«O» большое и «o» малое

«O» большое и «o» малое (${\displaystyle O}$ и ${\displaystyle o}$) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. Под асимптотикой понимается характер изменения функции при стремлении её аргумента к определённой точке.

${\displaystyle o(f)}$, «о малое от ${\displaystyle f}$» обозначает «бесконечно малое относительно ${\displaystyle f}$»[1], пренебрежимо малую величину при рассмотрении ${\displaystyle f}$. Смысл термина «О большое» зависит от его области применения, но всегда ${\displaystyle O(f)}$ растёт не быстрее, чем ${\displaystyle f}$ (точные определения приведены ниже).

В частности:

• фраза «сложность алгоритма есть ${\displaystyle O(f(n))}$» означает, что с увеличением параметра ${\displaystyle n}$, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем ${\displaystyle f(n)}$, умноженная на некоторую константу;
• фраза «функция ${\displaystyle f(x)}$ является „о“ малым от функции ${\displaystyle g(x)}$ в окрестности точки ${\displaystyle p}$» означает, что с приближением ${\displaystyle x}$ к ${\displaystyle p}$ ${\displaystyle f(x)}$ уменьшается быстрее, чем ${\displaystyle g(x)}$ (отношение ${\displaystyle \left|f(x)\right|/\left|g(x)\right|}$ стремится к нулю).