Тета большое

Через Θ(f) (читается тета большое) мы обозначаем класс функций, растущих с той же скоростью, что и f. С формальной точки зрения этот класс представляет собой пересечение двух предыдущих классов, Θ(f) = Ω(f) ⋂ Ο(f). 

O большое

На другом конце спектра находится класс O(f) (читается о большое). Этот класс состоит из функций, растущих не быстрее f. Функция f представляет собой верхнюю границу класса O(f). С формальной точки зрения g принадлежит классу O(f), если g(n) ⩽ cf(n) для всех n, начиная с некоторого порога n₀, и для некоторой положительной константы c.

Проверить, принадлежит ли данная функция классу O(f), можно двумя способами: либо с помощью данного выше определения, либо воспользовавшись следующим описанием: g ∈ O(f), если \lim_{n\to\infty}\frac{g(n)}{f(n)}=c для некоторой константы c. Это означает, что если предел отношения g(n)/f(n) существует и он меньше бесконечности, то g ∈ O(f). Для некоторых функций это не так-то просто проверить. По правилу Лопиталя, в таком случае можно заменить предел отношения самих функций пределом отношения их производных.

Омега большое

Класс функций, растущих по крайней мере так же быстро, как f, мы обозначаем через Ω(f) (читается омега большое). Функция g принадлежит этому классу, если при всех значениях аргумента n, больших некоторого порога n₀, значение g(n) > cf(n) для некоторого положительного числа c. Можно считать, что класс Ω(f) задаётся указанием своей нижней границы: все функции из него растут по крайней мере так же быстро, как f.

Скорости роста функций

Графики четырех функций:

https://ggbm.at/GWhpSG98

Функция содержащая x², сначала растёт медленно, однако чем больше x, тем выше скорость роста функции. Скорость роста функций, содержащих x, постоянна всем интервале значений переменной. Функция 2logx вообще кажется постоянной, но это обман зрения. На самом деле она растёт, только очень медленно. Относительная высота значений функций также зависит от того, большие или маленькие значения переменной мы рассматриваем. Сравним значения функций при x = 2. Функцией с наименьшим значением в этой точке является x²/8, а с наибольшим - функция x+10. Однако с возрастанием x функция x²/8 становится и остаётся впоследствии наибольшей.