Would I use the third case of the Master Theorem for the recurrence equation $T(n) = 2T(n/2) + n^{2}\log n$?

The condition given for the third case by Wikipedia is $f(n) = \Theta(n^c)$ when $c > \log_{b}a$.


Yes and no. The form of the Master Theorem given on Wikipedia is a bit more restrictive than a fuller version of the theorem, essentially limiting itself to the cases where $f(n)$ is a polynomial.

In this case, where $f(n) \notin \Theta(n^{c})$ for any $c$ (though we do have $f(n) \in \Omega(n^{2})$ and $f(n) \in O(n^{2+\varepsilon})$ for any $\varepsilon > 0$), the condition given on Wikipedia is insufficient.

A more useful (but slightly mathematically harder to work with, sometimes) formulation can be found in Cormen et al.'s "Introduction to Algorithms", or in this convenient worksheet from MIT.

The third case in this version is now

If $$ f(n) \in \Omega(n^{\log_{b}(a)+\varepsilon}) \text{ with } \varepsilon > 0 $$ where $f(n)$ also has to satisfy a "regularity condition": $$ a f(\frac{n}{b}) \leq cf(n) \text{ for some } c>1 \text{ and } n \text{ large enough} $$ then $$ T(n) \in \Theta(f(n)) $$

For the recurrence $T(n) = 2T(\frac{n}{2})+n^{2}\log n$, we have $\log_{b}a = 1$, so we can pick any $\varepsilon \in (0,1]$ (say for the sake of argument we pick $\varepsilon = 1$) and we have $f(n) \in \Omega(n^{1+\varepsilon}) = \Omega(n^{2})$.

Thus we can conclude $T(n) \in \Theta(n^{2}\log n)$.

In this case we don't need to worry too much about the regularity condition as $n^{2}\log n$ is well behaved - the condition is there to stop tricky things like the ones mentioned in the Wikipedia article, such as $f(n)=n\cdot(2-\cos n)$.


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.