# How to find recurrences where Master formula cannot be applied

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

How do you solve such a recurrence?

-

## migrated from cstheory.stackexchange.comDec 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
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
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}})$