edited by
5,062 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 ?
edited by

4 Answers

Best answer
1 votes
1 votes

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

i think it is Correct using Extend master method ..

Related questions

0 votes
0 votes
1 answer
1
lucasbbs asked Feb 28, 2022
6,581 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...
5 votes
5 votes
1 answer
2
1 votes
1 votes
2 answers
4
mdboi asked Oct 28, 2022
742 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n