o-малое: пренебрежимо меньший рост

Как в учебнике

Пусть $f(n)\ge0$ и $g(n)>0$ при достаточно больших натуральных $n$. Запись $f\in o(g)$ означает $\lim_{n\to\infty}f(n)/g(n)=0$. Сравнивается относительный размер функций, а не их абсолютные значения.

Равносильно: для любого $\varepsilon>0$ существует $n_0$, после которого $f(n)\le\varepsilon g(n)$. В отличие от O-большого, разрешённый множитель можно потребовать сколь угодно малым, сдвигая порог начала хвоста.

Например, $n\in o(n^2)$, поскольку отношение равно $1/n\to0$. Сама функция $n$ при этом не уменьшается и не стремится к нулю. Но $3n\notin o(n)$: отношение постоянно равно 3, хотя обычная верхняя оценка $3n\in O(n)$ верна.

Пренебрежимость здесь асимптотическая: на небольшом входе константы могут сделать меньший порядок численно значительным. Исключение слагаемого из конкретного расчёта требует проверки его относительного вклада на используемом масштабе.

Порог $n_0$ разрешено выбирать заново для каждого $\varepsilon$, но после выбора условие должно выполняться для всех больших $n$. Отдельные удачные значения отношения недостаточны. При положительных функциях умножение $f$ на любую фиксированную положительную константу сохраняет принадлежность $o(g)$: константа меняет требуемый порог, но нулевой предел отношения остаётся нулевым.

Определения и обозначения: Mathematics for Computer Science.

Связанные понятия: Предел последовательности, O-большое: верхняя оценка роста.