I Wrote an algorithm whose running time is described by the recurrence
$$T(n) = 2T(n/2) + \Theta(n\lg n),$$
and I want to determine whether $T(n) = o(n^2)$.
Now by the third case of the "Master Theorem" a recurrence of the form
$$T(n) = 2T(n/2) + f(n)$$
has solution $T(n) = \Theta(f(n))$, if $f(n) = \Omega(n^{1+\varepsilon})$ for some $\varepsilon > 0$.
I can't apply this directly to my recurrence since $n\lg n \neq \Omega(n^{1+\varepsilon})$, but if I can find a function $f(n)$ such that
$$n\lg n = \Omega(f(n))\qquad \text{ and } \qquad f(n) = \Omega(n^{1+\varepsilon}) \qquad\text{ and } \qquad f(n) = o(n^2),$$
then I can just use the master theorem on
$$T(n) = 2T(n/2) + f(n)$$
to get the bound. So is there such an $f(n)$?
Best Answer
None of the Master Theorem's cases apply to your problem. In order to find the asymptotic running time of your recurrence, you need an extended version described in exercise 4.6-2 of CLRS book (extension of Case 2). Besides the Wikipedia to which Ian already referred, see also here or here for a proof of this case extension.
So you have $a=b=2, k=1$, and you get $T(n)=\Theta(n\lg^2n)=o(n^2)$