$T(n) = 4T(\sqrt n) + n$

First I substitute n = $2^k$:

$T(2^k) = 4T(2^{k/2}) + 2^k$

Now I rename the above as follows:

$S(k)=4S(k/2) + 2^k$

Now if I try to use tree method on this in the following way:

Work done at Level 1 = $2^k$

Work done at Level 2 = $2^{k/2} * 4$

Work done at Level 3 = $2^{k/4} * 16$ and so on. We have a total of $log\ k$ levels. The final term is dominant. So we should get $2^{k/{2^{log\ k}}} * (log\ k)^2$

That gives me the answer as $T(n)=(log\ k)^2$ = $(log\ log\ n)^2$

Second method:

$T(2^k) = 4T(2^{k/2}) + 2^k$

Divide each term by $2^k$:

$T(2^k)/2^k = 2T(2^{k/2})/2^{k/2} + 1$

Now rename it as follows:

$S(k)=2S(k/2) + 1$

Now using masters theorem on the above gets us $T(n) = k = log\ n$

The actual answer seems to be $n$. So, where am I making the mistake? Please let me know the the mistake in both the methods.

(Note: I actually mean asymptotic notation as the final answer).


1 Answer 1


For your first method, it is dominated by the first term, not the last. (The second term is $2^{k/2} * 4 = 2^{(k/2)+2} < 2^k$ for $k$ large.)

In your second method, when you divide each term by $2^k$, you didn't. You divided the second term by $2^{(k/2)+1}$ instead.

  • $\begingroup$ I got the mistake in first method. However, I'm not able to get answer by second method. Can you give me some hints on how to do it using second method? $\endgroup$
    – aste123
    Commented Jan 26, 2017 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.