2.4.1 Сложение функций

Сумма двух функций определяется доминантной функцией
$f(n)+g(n)=\Theta(max(f(n),g(n)))$
Это полезно при упрощении выражений. Например, из этого следует, что $n^3+n^2+n+1=O(n^3$). По сравнению с доминантным членом, все остальные несущественные.

2.4.2 Умножение функций

Умножение можно представить как повторяющееся сложение, умножение функции на константу не может повлиять на ее асимптотическое поведение, поскольку при анализе функции мы можем умножить константу с на 1/с, чтобы привести их в соответствие

$$ O(cf(n)) \to O(f(n)) $$ $$ \Omega(cf(n)) \to \Omega(f(n)) $$ $$ \Theta(cf(n)) \to \Theta(f(n)) $$

Если обе функции произведения возрастают, то обе являются важными.

$$ O(f(n)) \cdot O(g(n)) \to O(f(n) \cdot g(n)) $$ $$ \Omega(f(n)) \cdot \Omega(g(n)) \to \Omega(f(n) \cdot g(n)) $$ $$ \Theta(f(n)) \cdot \Theta(g(n)) \to \Theta(f(n) \cdot g(n)) $$