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