Является ли временная сложность O (nlogn) + O (n) просто O (nlogn)?

Question

Допустим, у меня есть массив длины n, и я перебрал его, используя алгоритм сортировки со временем nlogn. После получения этого отсортированного массива я перебираю его, чтобы найти любые повторяющиеся элементы с линейным временем. Насколько я понимаю, поскольку операции происходили отдельно, это будет время O(nlogn) + O(n), а не O(nlogn+n). Если это так, то nlogn превысит линейную временную сложность, делая окончательную временную сложность O(nlogn)?

Answer 1

O (nlogn) + O (n) и не O (nlogn + n)

Нет такой вещи; O ( n log n ) + O ( n ) и O ( n log n + n ) равны, и оба равны O ( n log п ). Так что функция не может быть в одной, а не в другой.

Answer 2

да, поскольку log (n)> 1 для больших n, поэтому O (nlog (n)) является расширенным набором O (n)