1
$\begingroup$

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

I know that each $k$-th level is equal to $n^{1/2^k}$, and intuitively, $T(n) = \theta(\log_2(\log_2 n))$. I am just not certain where the constant 5 goes in the substitution method, and how I can generate tight lower and upper bounds for this recurrence relation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.