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)?