Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$

Question

I need to find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$.

I thought first to make a substitution: $m=\log n$. Then: $$ T(2^m)=T(2^{m \over 2})+10\log m $$ Let $S(m)=T(2^m)$: $$ S(m)=S\big({m \over 2}\big)+10\log m $$

Now we can use Master theorem.

Suppose it's the case when $f(m)=O(m^{\log_2 1-\epsilon})=O(m^{0-\epsilon})$. Let $\epsilon=0.5$ then: $$ \lim_{n\to \infty}\frac{10\log m}{m^{0.5}}=0 $$ Hence according to the Master theorem $T(m)=\Theta(m^0)=\Theta(1)$.

Am I in the right direction?

Answer 1

We can expand the recursion (ignoring the constant 10) as follows: $$ \begin{align*} T(n) &= \log \log n + \log \log n^{1/2} + \log \log n^{1/4} + \log \log n^{1/8} + \cdots \\ &= \log \log n + \log \frac{1}{2} \log n + \log \frac{1}{4} \log n + \log \frac{1}{8} \log n + \cdots \\ &= \log \log n + (\log \log n - \log 2) + (\log \log n - \log 4) + (\log \log n - \log 8) + \cdots \end{align*} $$ At this point, let us notice that the number of terms is roughly the value of $k$ satisfying $n^{1/2^k} = \Theta(1)$, which translates to $\frac{\log n}{2^k} = \Theta(1)$ and so $\log n = \Theta(2^k)$, implying $k \approx \log_2 \log n = (\log \log n)/\log 2$. Keeping $k$ symbolic at first, we have $$ \begin{align*} T(n) &= k \log\log n - (\log 2)(0 + 1 + 2 + 3 + \cdots + (k-1)) \\ &= k \log\log n - \frac{\log 2}{2} k(k-1) \\ &\approx k \left(\log\log n -\frac{\log 2}{2} k \right). \end{align*} $$ Substituting our approximation for $k$, we deduce $$ T(n) \approx \frac{\log \log n}{\log 2} \left(\log\log n - \frac{\log\log n}{2}\right) = \frac{(\log \log n)^2}{2\log 2}. $$ In particular, $T(n) = \Theta((\log \log n)^2)$.

Answer 2

An alternative solution still using domain transformation/change of variables.

$$T(n) = T(\sqrt{n}) + \log \log n$$

1. Let $m = \log n$

We can then define a new function $S$ based on how $m$ changes in $T$ and expand it:

$$\begin{align} S(m) &= S\left(\frac{m}{2}\right) + \log m\\ &=S\left(\frac{m}{4}\right) + \log m -1 + \log m\\ & \vdots\\ & = \log^2 m - \sum_{i = 1}^{\log m} i \\ & = \Theta(\log^2 m) \implies T(n) = \Theta((\log \log n)^2) \end{align}$$

2. Let $k = \log \log n$

We can then define a new function $R$ based on how $k$ changes in $T$ and expand it:

$$\begin{align} R(k) &= R(k - 1) + k\\ & = R(k - 2) + k - 1 + k\\ & \vdots\\ & = \Theta(k^2) \implies T(n) = \Theta((\log \log n)^2) \end{align}$$

Answer 3

Suppose $n=2^k.$

By substitution method we can extend the recurrence relation as follow: $$T(n)=T(\sqrt{n})+\log\log n$$ $$=\hspace{4pt} T\left(\sqrt{\sqrt{n}}\right)+\log\log n+10\log\log\sqrt{n}$$ $$=\hspace{4pt} T\left(\sqrt{\sqrt{\sqrt{n}}}\right)+\log\log n+\log\log\sqrt{n}+\log\log\sqrt{\sqrt{n}}$$

$$\dots =\hspace{4pt}T\left(n^{\frac{1}{2^k}}\right)+\log\log n+\log\log\sqrt{n}+\log\log\sqrt{\sqrt{n}}+\dots+\log\log n^{\frac{1}{2^{k-1}}}$$

After simplifying the logarithm terms: $$\dots =\hspace{4pt}T\left(n^{\frac{1}{2^k}}\right)+\log\log n+\log\left(\frac{\log n}{2}\right)+\log\left(\frac{\log n}{4}\right)+\dots+\log\left(\frac{\log n}{2^{k-1}}\right)$$ Next step is trying to find the value $k$: $$ n^{\frac{1}{2^k}}=\mathcal{O}(1)\implies k=\log\log n$$ (In essence, we need the height of recursion tree $\mathcal{T}$ that you can define the height $\mathcal{H}(n)$ of $\mathcal{T}$ as a recursion formula $\mathcal{H} (n)=\mathcal{H} (\sqrt{n})+1$, after solving it you get $\mathcal{H}(n)=\mathcal{O}(\log \log n).$

Finally we can write $T(n)$ as a summation: $$T(n)=\mathcal{O}(1)+\sum_{i=0}^{\log\log n} \log \left(\frac{\log n}{2^i}\right)$$ $$=\hspace{4pt} \mathcal{O}(1)+\sum_{i=0}^{\log\log n} (\log \log n- i)$$

$$=\hspace{4pt} \mathcal{O}(1)+\sum_{i=0}^{\log\log n} i=\theta(\log^2\log n)=\theta(\log\log n)^2$$