Let $$T(n) = 2T(n/2) +n \log(n)$$ Why does this fall under the second case? after applying the logic i get that $$n^{\log_22} = n$$ Than follows $$n < nlog(n)$$ So isn't this suppose to fall under the third case? Thanks!
Master theorem: https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
From Introduction to Algorithms by CLRS, for the case $3$ of the master theorem
If $f(n) = \Omega\left(n^{\log_ba+\epsilon}\right)$ for some constant $\epsilon > 0$, and if $af(n/b)\le cf(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.
We have $f(n) = n\log n$ and $n^{\log_ba+\epsilon} = n^{\log_22+\epsilon} = n^{1 + \epsilon}$. Note that $n\log n$ is not $\Omega\left(n^{1 + \epsilon}\right)$ because $n\log n$ grows faster than $n$ but not faster than $n^{1 + \epsilon}$ for any $\epsilon > 0$, and so the third case of the master theorem does not apply.
