[Solved]: Master theorem for $T(n) = 2T(n/2) + n^{2}\log n$

Problem Detail: 

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

Asked By : Voltemand11

Answered By : Luke Mathieson

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19077

3.2K people like this

 Download Related Notes/Documents