Is nlog(n) Big Theta(n)? Master Theorem

Question

Is n⋅log(n) in Θ(n)?
Im asking this because I am solving reccurrences using the master theorem.

The equation is T(n) = 2T(n/2) + n log n

The solution says that it fulfills case 2, meaning T(n) = Θ(n log(n)).

I don't understand how n log(n) could be O(n), shouldn't n log(n) be greater than n when n > 10?

Answer 1

No, n log n ≠ Θ(n). To see this, notice that

lim_{n → ∞} ((n log n) / n) = lim_{n → ∞} log n = ∞

Since this limit tends toward infinity, we see that n log n is not Θ(n). Did you find a source that says otherwise?

Hope this helps!