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