Расчет обозначений Big-O, O (n) * O (log n) = O (n log n)

Question

Мне нужно разработать алгоритм, который мог бы выполнять некоторые вычисления в заданной O-записи.Прошло некоторое время с тех пор, как я в последний раз вычислял с помощью нотации O, и я немного запутался в том, как добавлять разные нотации O вместе.

O(n) * O(log n) = O(n log n)

O(n) + O(n) = O(2n) = O(n)

O(n) * O(log n) + O(n log n) = O(n log n) + O(n log n) = O(n log n)

Это правильно?Какие еще правила я пропустил?

Answer 1

Правило для умножения действительно простое:

O(f) * O(g) = O(f * g)

Сумма двух O членов сложнее вычислить, если вы хотите, чтобы она работала для произвольных функций.
Однако, если f ∈ O(g), то f + g ∈ O(g).

Таким образом, ваши расчеты верны, а ваш первоначальный заголовок - нет;

O(n) + O(log n) = O(n)