$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).
Solving recurrence relations using substitution followed by tree method/masters theorem
asymptotics;recurrence relation;discrete mathematics;master theorem