1
$\begingroup$

So apparently:

$T(n) = 2T(n/2) + n / \log n$ doesn't work with the Master Theorem because of the log term.

But then:

$T(n) = 4T(n/2) + n / \log n$ is $\Theta(n^2)$ even though it's still the same log term.

Why is this the case?

$\endgroup$
1
  • 1
    $\begingroup$ @DietrichBurde I am asking about $n$ divided by $\log n$, not $n \log n$ $\endgroup$
    – AJJ
    Jan 1 '16 at 19:10
2
$\begingroup$

The Master Theorem lets one handle (many) recurrence relations of the form $$ T(n) = aT\left(\frac{n}{b}\right) + f(n) $$ where $a\geq 1$ and $b > 1$. The key is to compare the function $f(n)$ to the quantity $\gamma\stackrel{\rm def}{=} \log_b a$.

In your two examples, $f(n)=\frac{n}{\log n}$; in the first case you have $a=b=2$ and $\gamma=1$. Therefore, $f(n)$ is not $O(n^c)$ for any $c< \gamma$, nor $\Theta(n^\gamma\log^k n)$ for any $k\geq 0$, nor $\Omega(n^c)$ for any $c>\gamma$: none of the 3 cases of the Master Theorem apply (although we are "pretty close" to the first). We cannot conclude, because the $\log n$ factor blurs the line between what part of the recurrence dominates: the overhead $f(n)$ at each step, or the branching factor (from one step to $a$ smaller substeps).

But in the second case, $a=4$, $b=2$, and thus $\gamma=2$. In this case, we do have $f(n) = O(n^c)$ for some $c < \gamma$ (taking $c=1$ works), and the first case of the Master theorem applies: we get $T(n) = \Theta(n^\gamma) = \Theta(n^2)$.

In a nutshell: the difference between the two cases you gave is not in $f(n)$, it is in the rest of the recurrence (the constant $a$), which allows the branching in the recurrence to dominate the complexity (each step gives rise to 4 substeps, not 2 as before, so they add up much more quickly.)

$\endgroup$
7
  • $\begingroup$ Also, and while this is not the original question, for completeness: the case above, not handled by the Master Theorem, can still be dealt with using the Akra–Bazzi method, or "manually" e.g. by studying $T^\prime(k) = \frac{T(2^k)}{2^k}$ instead. Both will lead to $T(n) = \Theta(n \log\log n)$ (i.e., $T^\prime(k) = \Theta(\log k)$, that is $T(2^k) = \Theta(2^k \log k))$). $\endgroup$
    – Clement C.
    Jan 1 '16 at 21:56
  • $\begingroup$ Does Akra-Bazzi do everything the Master Theorem does? $\endgroup$
    – AJJ
    Jan 1 '16 at 21:57
  • $\begingroup$ Yes -- it is a strict generalization, iirc. $\endgroup$
    – Clement C.
    Jan 1 '16 at 21:57
  • $\begingroup$ So far I've mostly been doing this with the Master Theorem: Compare $O(n^{\log_b(a)})$ with $O(f(n))$, ignoring any log factors, and see which one has the higher complexity (and that will be the answer), unless they're the same, then the runtime is $f(n) \log n$. This seems to work for every case I've tried so far except for the ones I described above. $\endgroup$
    – AJJ
    Jan 1 '16 at 21:59
  • $\begingroup$ Is there an easy way to use Akra Bazzi? $\endgroup$
    – AJJ
    Jan 1 '16 at 22:09

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.