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

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?

• We don't grade answers here. Keep working until you get an answer. If all steps you did along the way were valid, then you will have found the correct answer. – Yuval Filmus Jul 13 '17 at 16:42
• @YuvalFilmus I don't think the answer is correct actually I now realized that $f(m)\neq O(m^{0-\epsilon})$. I don't think master theorem is applicable here right? – Yos Jul 13 '17 at 16:44
• @YuvalFilmus on a separate note, I didn't make up the tag "check-my-answer" so I don't think I'm misusing the platform in any way. I think it's always better to show your line of thinking and get feedback as opposed to just ask a question and receive an answer. – Yos Jul 13 '17 at 16:48
• Possible duplicate of Run time of a Simple Recurrence – ryan Jul 13 '17 at 17:20
• Yos, you might want to look at the guidance for the check-my-answer tag: cs.stackexchange.com/tags/check-my-answer/info. As Yuval says, we discourage "please check whether my answer is correct" questions, as they tend not to be interesting or useful to future visitors. See here and here. – D.W. Jul 13 '17 at 17:35

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

• Wow. Why $n^{1/2^k} = \Theta(1)$? As far as I understand $k$ is the height of the tree of recursion? Then wouldn't it be $2^k=n$ but because we have $T(\sqrt{n})$ I'd figure $(2^k)^{1/2}=n^{1/2} \Leftrightarrow 2^{k/2}=\sqrt n \Rightarrow n=\log{k \over 2}$ – Yos Jul 13 '17 at 17:25
• The recursion stops once you reach some base case, and this happens when $n^{1/2^k}$ dips below some constant. – Yuval Filmus Jul 13 '17 at 17:26

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}

• if $m=\log n$: let $m=2^k$ then as far as I understand the development is $\log m+\log{m \over 2}+\log{m \over 4}+...+\log{m \over k}=\log m+\log m -\log 2+ \log m -\log 4+...+\log m-\log k=m\cdot \log m-\sum_{i=1}^{2^k}\log 2^i=m\cdot \log m-\frac{\log m(\log m +1)}{2}=m\cdot \log m-{1 \over 2}(\log^m+\log m)=\Theta \log ^m$. Is this correct? – Yos Jul 13 '17 at 17:53
• I've made one edit expanding the step you mention. The problem in your comment is $\dots \neq m \cdot \log m - \dots$, it should be $= \log m \cdot \log m - \dots$, because the expansion will only continue as many steps as we can divide $m$ by $2$, which would be $\log m$. – ryan Jul 13 '17 at 18:06
• I kinda hid the assumption that $n = 2^{2^k}$ and also hid the assumption that log bases were 2 but that's typically assumed. So we then have $\sqrt{2^{2^k}} = 2^{2^{k-1}}$. Check here for more info. – ryan Jul 13 '17 at 18:25
• The point of $R$ is to represent just how $k$ changes in the recurrence $T$. $R$ is different than $T$, but if we get a bound on $R$ we can infer a bound on $T$. Establishing $T(\sqrt{n}) = T(2^{2^{k-1}})$ would leave us in the same place we started just in a different form. $R$ abstracts the difficulties of $T$ by only dealing with the variable $k$ rather than $2^{2^k}$. – ryan Jul 13 '17 at 18:36
• It's just the sum of 1 to $\log m$. Check here. The main idea is that $\sum_1^n i = \Theta(n^2)$ for any $n$. – ryan Jul 13 '17 at 18:52