Dark Mode

3,946 views

2 votes

I've been struggling to come to exact solution for this. Master's theorem is not applicable and likely way to get to answer is Recursion tree. Which is giving me Theta(n) as an answer.

Steps : =>

1) T(n) = 2T(n/4) + √3

2) Emerging Pattern => (1/2^k) * n

3) Considering when we break down to T(1) : : (1/2^k) * n =1

4) k = log (n)

5) Each level has 2^i nodes :: 2^(log (n)) :=> n

6) If you sum up cost , n + n/2 + n/4 + ..... = n/2

Which is incorrect ,

Answer given is ( √n log n ) , would appreciate if someone could shed light how so ?

Steps : =>

1) T(n) = 2T(n/4) + √3

2) Emerging Pattern => (1/2^k) * n

3) Considering when we break down to T(1) : : (1/2^k) * n =1

4) k = log (n)

5) Each level has 2^i nodes :: 2^(log (n)) :=> n

6) If you sum up cost , n + n/2 + n/4 + ..... = n/2

Which is incorrect ,

Answer given is ( √n log n ) , would appreciate if someone could shed light how so ?

1 vote

Best answer

Extended Master theorem:

$T(n)=aT(n/b)+n^{k}log^{p}n$---->$(1)$

where $a\geq1,b>1,k\geq0$ and $p$ is any real number

Case$(1):$ If $a>b^{k}$

then $T(n)=\theta(n^{log_{b} a})$

Case$(2):$If $a=b^{k}$

If $(a) p>-1$

then $T(n)=\theta(n^{log_{b} a}log^{p+1}n)$

If $(b) p=-1$

then $T(n)=\theta(n^{log_{b} a}loglogn)$

If $(c) p<-1$

then $T(n)=\theta(n^{log_{b}a})$

Case$(3):$If $a<b^{k}$

if $(a)p\geq0$

then $T(n)=\theta(n^{k}log^{p}n)$

if $(b)p<0$

then $T(n)=\theta(n^{k})$

Let come to the question $T(n)=2T(n/4)+\sqrt{3}$

$T(n)=2T(n/4)+(3)^{\frac{1}{2}}$

Lets compare with equation $(1),$

$a=2,b=4,k=0,p=0$

Now $a>b^{k}$

$2>4^{0}$

So,Case $(1)$ is satisfied.

$T(n)=\theta(n^{log_{b}a})$

$T(n)=\theta(n^{log_{4}2})$

$T(n)=\theta(n^{log_{2^{2}}2})$

$T(n)=\theta(n^\frac{1}{2}{log_{2}2})$

$T(n)=\theta(n^\frac{1}{2})$

$T(n)=\theta(\sqrt{n})$

4 votes

In these type of questions where master method doesnt apply you can do the following

$T(n) = 2T(n/4) + \sqrt{3}$

Reframe it like this, by putting i in the specified positions

$T(n) = 2^{i}T(n/4^{i}) + i\sqrt{3}$

Now for n/4^{i} = 1, put i = log_{4}n

So the equation becomes

$T(n) = 2^{log_{4}n} + log_{4}n\sqrt{3}$

Or

$T(n) = n^{log_{4}2} + log_{4}n\sqrt{3}$

$T(n) = \sqrt{n} + log_{4}n\sqrt{3}$

And therefore

$T(n) = O(\sqrt{n})$

3 votes

Adding cost of each level;

$\begin{align*} T(n) &= 2^0.\sqrt{3} + 2^1.\sqrt{3} + 2^2.\sqrt{3} + .... + 2^{\log_4 n}.\sqrt{3} \\ &= \sqrt{3}.\left [ \frac{2^{\log_4 {n}+1}-1}{2-1} \right ] \\ &= \sqrt{3}.O(n^{\frac{1}{2}}) \\ &= O(\sqrt{n}) \end{align*}$

$\begin{align*} T(n) &= 2^0.\sqrt{3} + 2^1.\sqrt{3} + 2^2.\sqrt{3} + .... + 2^{\log_4 n}.\sqrt{3} \\ &= \sqrt{3}.\left [ \frac{2^{\log_4 {n}+1}-1}{2-1} \right ] \\ &= \sqrt{3}.O(n^{\frac{1}{2}}) \\ &= O(\sqrt{n}) \end{align*}$

This is right , I was summing up thinking it's √3n ; anyways I'm not able to figure out if √n * log n is wrong answer then ?

0

0 votes