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
0 comments:
Post a Comment
Let us know your responses and feedback