Почему Merge Сортировка по времени не O (N)?

Question

Merge время сортировки сложность O (N журнал N), поэтому здесь п доминируют на LOGN, так Merge сортировки является O (N)

Благодаря

Answer 1

O(n log n) это лучшее, что вы можете получить, используя Традиционная алгоритмы сортировки.

Вы не можете сказать, что O(n log n) == O(n), даже если n доминирует над logn, потому что они умножаются, не добавляя.

Если вы получили n + logn и n доминирует logn тогда вы можете сказать, что O является O(n)