3,946 views
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 ?

why masters theorem not applicable
Case (III) Regularity condition fails.
It is not case 3.  It is Case 1     $\sqrt {3}$ =$O(n^{1/2 - e})$
My bad , it is case (I) , but then  √3 =O(n1/2−e) does not always hold , so is it still valid ?

And , if you apply considering it does hold , answer given is ( √n log n ) and master's theorem would gives us √n .

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})$

### 1 comment

y can't we take k as1/2

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/4i = 1, put i = log4n

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})$

\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*}
by

### 1 comment

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 ?

i think it is Correct using Extend master method ..

why K=0 ???  can u explain Extend master method...

edited
Yes we can do using extended master theorem

1
917 views
1 vote