# Solving recurrence relations using substitution followed by tree method/masters theorem

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

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.