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?

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

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ok you solved this with substitution method.Is there no possibility to solve this by master therom? $\endgroup$
    – user1917769
    Sep 28, 2013 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, 2013 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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