Как мне выразить O (n) * O (n log n)

Question

Я пишу отчет, в котором мне нужно представить некоторые результаты с пометкой Big O.Поскольку я не использовал нотации Big O раньше, я немного не уверен в том, как писать.

Я понимаю, что если у вас O (n) * O (n), то результатом становится O (n ^2).Например, цикл в цикле.

И O (n) * O (log n) равно O (n log n). Например, если вам нужно зациклить функцию, которая ищет в сбалансированномдвоичное дерево.

Но если мне нужно зациклить функцию со временной сложностью O (n log n).

Как правильно написать O (n) * O (n log n)?

Answer 1

Это просто нормальное умножение всего, что находится внутри O.

n * n*log(n) = n^2*log(n)

Так что это:

O(n^2 log n)