Является ли nlog(n) Big Theta(n)? Основная теорема

Question

Находится ли n⋅log(n) в Θ(n)?
Я спрашиваю это, потому что я решаю повторения, используя основную теорему.

Уравнение T(n) = 2T(n/2) + n log n

Решение говорит, что оно удовлетворяет случаю 2, что означает T(n) = Θ(n log(n)).

Я не понимаю, как n log (n) может быть O (n), не должно ли n log (n) быть больше, чем n, когда n > 10?

Answer 1

Нет, n log n Θ Θ(n). Чтобы увидеть это, обратите внимание, что

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

Поскольку этот предел стремится к бесконечности, мы видим, что n log n не Θ(n). Вы нашли источник, который говорит иначе?

Надеюсь это поможет!

Answer 2

Θ(n⋅log(n)) - это не O(n), а O(n⋅log(n)), что является правильным решением.