Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Given: $T(n) = T(\sqrt{n}) + 1$ (base case $T(x) = 1$ for $x<=2$)

How do you solve such a recurrence?

share|improve this question

migrated from cstheory.stackexchange.com Dec 16 '12 at 19:46

This question came from our site for theoretical computer scientists and researchers in related fields.

    
Have a look here. –  Juho Dec 16 '12 at 19:50
3  
Hint: Let $n = 2^{2^k}$, so $\sqrt{n} = 2^{2^{k-1}}$, and take it from there. –  Yuval Filmus Dec 16 '12 at 20:04
add comment

1 Answer 1

up vote 7 down vote accepted

For the recurrence, $$ T(n) = T(\sqrt{n}) + 1 $$ Let $n = 2^{2^{k}}$, therefore we can write the recurrence as:

$$ T(2^{2^{k}}) = T(2^{2^{k-1}}) + 1 \\ T(2^{2^{k-1}}) = T(2^{2^{k-2}}) + 1 \\\ldots\\\\\ldots\\ T(2^{2^{k-k}}) = 1 $$

, i.e. $ k * O(1) $ work or linear in $k$. We can express $k$ in terms of $n$: $$ \log{n} = 2^{k} \\ \log{\log{n}} = k $$

Hence, the recurrence solves $T(n) = O(\log{\log{n}}) $

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.