World's most popular travel blog for travel bloggers.

# [Solved]: How to find recurrences where Master formula cannot be applied

, ,
Problem Detail:

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

How do you solve such a recurrence?

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}})$