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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 13 '17 at 16:42
  • $\begingroup$ @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? $\endgroup$ – Yos Jul 13 '17 at 16:44
  • 1
    $\begingroup$ @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. $\endgroup$ – Yos Jul 13 '17 at 16:48
  • 3
    $\begingroup$ Possible duplicate of Run time of a Simple Recurrence $\endgroup$ – ryan Jul 13 '17 at 17:20
  • $\begingroup$ 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. $\endgroup$ – 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)$.

  • $\begingroup$ 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}$ $\endgroup$ – Yos Jul 13 '17 at 17:25
  • 1
    $\begingroup$ The recursion stops once you reach some base case, and this happens when $n^{1/2^k}$ dips below some constant. $\endgroup$ – 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}$$

  • $\begingroup$ 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? $\endgroup$ – Yos Jul 13 '17 at 17:53
  • 1
    $\begingroup$ 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$. $\endgroup$ – ryan Jul 13 '17 at 18:06
  • 1
    $\begingroup$ 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. $\endgroup$ – ryan Jul 13 '17 at 18:25
  • 1
    $\begingroup$ 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}$. $\endgroup$ – ryan Jul 13 '17 at 18:36
  • 1
    $\begingroup$ 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$. $\endgroup$ – ryan Jul 13 '17 at 18:52

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.