5
$\begingroup$

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.

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$

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.