n log n это O (n)?

Я пытаюсь решить эту проблему

T (n) = 3 T (n / 2) + n lg n ..

Я пришел к решению, что оно принадлежит случаю 2 теоремы мастеров, поскольку n lg n есть O (n ^ 2)

но после обращения к руководству по решению я заметил это решение, которое они имеют

Решение говорит, что n lg n = O (n ^ (lg 3 - e)) для e между 0 и 0,58

так что это означает, что n lg n является O (n) .. это правильно? Я что-то здесь упускаю?

Разве это не nlgn O (n ^ 2)?

Ответы на вопрос(2)

Ваш ответ на вопрос