n log n равно O (n)?

Question

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

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 is O (n) .. это правильно?Мне что-то здесь не хватает?

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

Answer 1

Это лучше объяснит ситуацию

Answer 2

n*log(n) не является O(n^2).Он известен как квазилинейный и растет намного медленнее, чем кодовый код.Фактически, кодовый кодовый код меньше полинома.

Другими словами:

родовое слово

где создается кодовый код

В вашем примере:

родовое слово

Поскольку O(n^2) является полиномиальным и доминирует над n*log(n), последний член отпадает, поэтому окончательная сложность - это просто k > 1.

Answer 3

n ^lg3 не O (n).Он перерастает O (n) ... Фактически, любой показатель степени n, превышающий 1, приводит к асимптотически большему времени, чем O (n).Поскольку lg (3) составляет около 1,58, до тех пор, пока вы вычитаете из экспоненты менее 0,58, она асимптотически больше, чем O (n).