8
$\begingroup$

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.

$\endgroup$
  • 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$ – David Richerby Dec 8 '14 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 '14 at 13:38
4
$\begingroup$

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

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

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.