Recurrence and Big-O - Question 1) T(n)=T(√n)+Θ(log(log(n)) and T(2)=0.

Question

I'm trying to solve the recurrence. Runtimes and recurrence solutions. For initial conditions T(2) = 0, solve for;

T(n)=T(√n)+Θ(log(log(n))

(recursive relation). Accordingly, T(n) € O(?)

Answer 1

We can solve the recurrence using the iteration method. First we rewrite the recurrence:

$$ T(n) = T\left(\sqrt{n}\right) + \lg \lg n $$

with the substitution $n = 2^m$, getting:

$$ T(2^m) = T\left(2^{\frac{m}{2}}\right) + \lg m $$

We now solve the above recurrence using the iteration method. The first iteration being:

$$ T(2^m) = T\left(2^{\frac{m}{2}}\right) + \lg m $$

The second being:

$$ T(2^m) = T\left( 2^{\frac{m}{4}} \right) + 2 \lg m - \lg 2^0 - \lg 2^1 $$

After one more we get:

$$ T(2^m) = T\left( 2^{\frac{m}{8}} \right) + 3 \lg m - \lg 2^0 - \lg 2^1 - \lg 2^2$$

Now, it takes $\lg m$ iterations to reduce $2^m$ down to $2$. We now generalise to:

$$ T(2^m) = \lg^2 m - \sum_{k = 0}^{\lg m - 1} \lg 2^k $$

$$ T(2^m) = \lg^2 m - \sum_{k = 0}^{\lg m - 1} k $$

Computing the sum in the equation above we get:

$$ T(2^m) = \frac{1}{2} \left( \lg^2 m + \lg m \right) $$

So we have obtained an explicit form for $T(2^m)$. We can verify the validity of the form using induction:

$$ T(2^m) = T \left( 2^{\frac{m}{2}} \right) + \lg m $$

$$ T(2^m) = \frac{1}{2} \left( \lg^2 \frac{m}{2} + \lg \frac{m}{2} \right) + \lg m $$

$$ T(2^m) = \frac{1}{2} \left((\lg m - 1)^2 + \lg m - 1 \right) + \lg m $$

$$ T(2^m) = \frac{1}{2} \lg^2 m + \frac{1}{2} - \lg m + \frac{1}{2} \lg m - \frac{1}{2} + \lg m $$

$$ T(2^m) = \frac{1}{2} \left( \lg^2 m + \lg m \right) $$

And so we have computed the correct form of $T(2^m)$. Since $n = 2^m$ we get:

$$ T(n) = \frac{1}{2} \left( \lg^2 \lg n + \lg \lg n \right) $$

Which means $T(n) = O\left( \lg^2 \lg n \right)$.