# Why does the Master Theorem work for this example but not the other?

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?

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

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

• 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))$). Jan 1 '16 at 21:56
• Does Akra-Bazzi do everything the Master Theorem does?
– AJJ
Jan 1 '16 at 21:57
• Yes -- it is a strict generalization, iirc. Jan 1 '16 at 21:57
• 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.
– AJJ
Jan 1 '16 at 21:59
• Is there an easy way to use Akra Bazzi?
– AJJ
Jan 1 '16 at 22:09