Если функция A вызывает n ^ c функций B, которая выполняется за O (n ^ 2) времени, какова временная сложность функции A? Это просто полином (n ^ c), а c только что стал больше?
Если функция A вызывает другую функцию B , общая сложность является результатом сложностей A и B . Таким образом, в этом случае общая сложность составляет O ( n c · n 2 ) = O ( n c + 2 ).
Общие правила для продуктов :
ƒ 1 ∈ O ( g 1 ) и ƒ 2 ∈ O ( g 2 ) ⟹ ƒ 1 · ƒ 2 ∈ O ( g 1 · g 1 ) ƒ · O ( g ) ∈ O (ƒ · g )
ƒ 1 ∈ O ( g 1 ) и ƒ 2 ∈ O ( g 2 ) ⟹ ƒ 1 · ƒ 2 ∈ O ( g 1 · g 1 )
ƒ · O ( g ) ∈ O (ƒ · g )