Problem Detail: Given: $T(n) = T(sqrt{n}) + 1$ (base case $T(x) = 1$ for $x<=2$) How do you solve such a recurrence?
Asked By : ajmartin
Answered By : ajmartin
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}}) $
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7445 3.2K people like this
