in Algorithms edited by
3,946 views
2 votes
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 ?
in Algorithms edited by
3.9k views

4 Comments

why masters theorem not applicable
0
0
Case (III) Regularity condition fails.
0
0
It is not case 3.  It is Case 1     $\sqrt {3}$ =$O(n^{1/2 - e})$
0
0
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 .
0
0

4 Answers

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

edited by

1 comment

y can't we take k as1/2
0
0
4 votes
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/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})$

3 votes
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*}$
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 ? 

0
0
0 votes
0 votes

i think it is Correct using Extend master method ..

2 Comments

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

0
0
edited by
Yes we can do using extended master theorem
0
0

Related questions