Сложение и умножение в O-символике
Правило суммы. Если 
и 
, то 
. (Аналогичные утверждения справедливы также для множеств 
и 
).
Доказательство. (Доказательство этой теоремы основывается простом соотношении для произвольных вещественных чисел 
, 
,
,
: если 
и 
, то 
)
Поскольку 
, существует константа с1 и неотрицательное целое число n1 такие, что для всех 
справедливо 
.
По аналогии, поскольку 
существует константа 
и неотрицательное целое число 
такие, что для всех 
справедливо 
.
Обозначим через 
и рассмотрим случай, когда верны оба неравенства для случая 
. Сложив приведенные выше неравенства, получим
.
Откуда следует, что . Исходя из определения О-асимптотики, в качестве констант с и 
положим 
и 
.
При анализе алгоритмов теорема о сумме используется следующим образом. Пусть имеются два фрагмента программы P2 и P2, причем время выполнения одного 
, а другого 
. Очевидно, что если эти фрагменты выполняются последовательно, то общее время работы (общая трудоемкость последовательно выполняемых фрагментов) будет равно 
. Тогда асимптотическая оценка всего фрагмента по теореме о сумме – 
. Это означает, что общая эффективность алгоритма зависит от той части, для которой функция роста трудоемкости имеет наибольший порядок роста, т.е. от наименее эффективной его части алгоритма:
.
Правило произведений. Если T1(n) и Т2(п) имеют степени роста O(f1(n)) и O(f2(n)) соответственно, то произведение T1(n)T2(n) имеет степень роста O(f1(n) f2(n)).
Доказательство аналогично доказательству правило сумм.
Следствие правила произведений. O(cf(n)) эквивалентно О(f(п )), где с — положительная константа. Иными словами положительную константу можно вносить и выносить из-под асимптотической функции.
Например, О(2п2) эквивалентно О(п2).