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