I want to prove that the time complexity of an algorithm is polylogarithmic in the scale of input.

The recurrence relation of this algorithm is $T(2n) \leq T(n) + T(n^a)$, where $a\in(0,1)$.

It seems that $T(n) \leq \log^{\beta}{n}$ for some $\beta$ depends on $a$. But I can't prove this inequality. How to solve this recurrence relation?

I just want to get an upper bound polylogarithmic in n.

  • 1
    $\begingroup$ $a<1$, I assume? Also, did you check our reference question? I don't think the specific case you're asking about is explicitly covered there but there are lots of techniques described. $\endgroup$ Dec 8, 2014 at 13:21
  • 1
    $\begingroup$ There's no "master" theorem for this type which I'm aware of; cf this question of mine and this one. (cc @DavidRicherby) $\endgroup$
    – Raphael
    Dec 8, 2014 at 13:38

1 Answer 1


Your guess is wrong. In fact, it is not hard to show that assuming $T(n) > 0$ for all $n > 0$, then $T(n) = \Omega(\log^k n)$ for all $k$. Indeed, for this to hold we need that for large enough $n$ we would have $$ (1+a^k) \log^k n = \log^k n + \log^k n^a \geq \log^k (2n), $$ or $\sqrt[k]{1+a^k} \log n \geq \log n + \log 2$, which holds as long as $[\sqrt[k]{1+a^k}-1]\log n \geq \log 2$, and in particular for large enough $n$.

What is the correct order of growth of $T(n)$? To try and find out, write $S(n) = T(2^n)$. The recurrence now becomes $$ S(n+1) = S(n) + S(an). $$ For large $n$, we would expect $S(n+1) - S(n)$ to be very close to $S'(n)$, and so heuristically we would expect that $S$ satisfy $S'(n) = S(an)$. This equation seems a bit hard to solve, but an approximate solution is $S(n) = n^{\Theta(\log n)}$. Substituting back, we deduce that the order of growth of $T(n)$ should be something like $(\log n)^{\Theta(\log \log n)}$.

  • $\begingroup$ It seems that $\log^k(2n) = (\log 2 + \log n)^k$. The Lower bound doesn't hold. $\endgroup$
    – Qiang Li
    Dec 28, 2014 at 6:14
  • $\begingroup$ @QiangLi Thanks for spotting the error. The lower bound does hold, however, once the argument is suitably modified. $\endgroup$ Dec 28, 2014 at 7:33

Your Answer

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

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