Пусть даны две функции f(n) и g(n) натурального аргумента n, значениями которых являются положительные действительные числа. Говорят, что
$f = O(g)$ (f растет не быстрее g), если существует такая константа c > 0 и номер N $\in \N$, что $f(n) ≤ c * g(n)$ для $\forall$ n > N.
Запись f = O(g) можно читать как “ f ≤ g с точностью до константы”.
Функцию g также называют *модельной функцией (*относительно которой мы проверяем функцию f).
Обозначение O(f) можно считать аналогом математической операции ≤. Для ≥ и = приняты следующие обозначения:
f = Ω(g)** – (омега, f растет не медленнее g с точностью до константы), g = O(f)
f = ϴ(g)** – (тэта, f и g имеют одинаковый порядок роста), f = O(g) и g = O(f)