# Solving a complicated recurrence relation

How to solve the recurrence relation below?

$$T(n) = \begin{cases} 2T(\sqrt{n}) + \log n/\log\log n & \text{if } n > 4\\ 1 & \text{if } n \leq 4. \end{cases}$$

Preferably by the master theorem; otherwise by any method. I know the Master Theorem fails, but is there any extension for these type of problems?

• Set $n = 2^m$ results in $T(2^m) = 2T(2^{m/2}) + \frac{m}{\log m}$, thus setting $S(m) = T(2^m)$, you should be able to apply the Master Theorem on $S$. – Tpecatte Sep 28 '13 at 14:43
• Can you apply any of those three rules on this relation? – user1917769 Sep 28 '13 at 15:20

Following Timot's suggestion, let $S(m) = T(2^m)$, so that $S$ satisfies the recurrence $$S(m) = \begin{cases} 2S(m/2) + \tfrac{m}{\log m} & \text{ if } m > 2 \\ 1 & \text{ otherwise.} \end{cases}$$ In fact, we'll analyze the recurrence with a base case of $m = 1$ instead, and assume the logarithm is base $2$. We have \begin{align*} S(2^k) &= \frac{2^k}{k} + 2 \frac{2^{k-1}}{k-1} + 4 \frac{2^{k-2}}{k-2} + \cdots + 2^{k-1} \frac{2^1}{1} + 2^k \\ &= 2^k \left[ \frac{1}{k} + \frac{1}{k-1} + \cdots + \frac{1}{1} + 1 \right] = \Theta(2^k\log k). \end{align*} Therefore $S(m) = \Theta(m\log\log m)$ and $T(n) = \Theta(\log n\log\log\log n)$.
• You can solve it using the Akra-Bazzi theorem. If your version of the master theorem can handle recurrences of the form $X(n) = aX(n/b) + f(n)$ for $f = n^\alpha(\log n)^\beta$, then it can handle the present recurrence (such a theorem can be stated), otherwise it cannot. Also consider the possible outcomes in your version of the master theorem - is $\Theta(m\log\log m)$ one of them? If not, you can't possibly use your theorem to deduce such a solution. – Yuval Filmus Sep 28 '13 at 22:23