debugMinor
How to find recurrences where Master formula cannot be applied
Viewed 0 times
cannotrecurrenceshowwhereappliedmasterfindformula
Problem
Given: $T(n) = T(\sqrt{n}) + 1$ (base case $T(x) = 1$ for $x<=2$)
How do you solve such a recurrence?
How do you solve such a recurrence?
Solution
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}}) $
$$
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}}) $
Context
StackExchange Computer Science Q#7445, answer score: 7
Revisions (0)
No revisions yet.