snippetMinor
How to solve $T(n)= 4T(\sqrt n) +\log^2n$?
Viewed 0 times
sqrtlogsolvehow
Problem
Consider the recurrence
$$T(n)= 4T(\sqrt n) + \log^2n. $$
I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
$$T(n)= 4T(\sqrt n) + \log^2n. $$
I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
Solution
Let $S(n) = T(2^n)$. Then
$$
S(n) = T(2^n) = 4T(2^{n/2}) + n^2 = 4S(n/2) + n^2.
$$
You can solve this recurrence using the master theorem, and then use $T(n) = S(\log n)$ to obtain a solution for the original recurrence.
$$
S(n) = T(2^n) = 4T(2^{n/2}) + n^2 = 4S(n/2) + n^2.
$$
You can solve this recurrence using the master theorem, and then use $T(n) = S(\log n)$ to obtain a solution for the original recurrence.
Context
StackExchange Computer Science Q#118210, answer score: 8
Revisions (0)
No revisions yet.