1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Tpecatte Sep 28 '13 at 14:43
  • $\begingroup$ Can you apply any of those three rules on this relation? $\endgroup$ – user1917769 Sep 28 '13 at 15:20
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ok you solved this with substitution method.Is there no possibility to solve this by master therom? $\endgroup$ – user1917769 Sep 28 '13 at 18:46
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 28 '13 at 22:23

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.