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

«O» большое и «o» малое ( и ) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. Под асимптотикой понимается характер изменения функции при стремлении её аргумента к определённой точке. , «о малое от » обозначает «бесконечно малое относительно », пренебрежимо малую величину при рассмотрении . Смысл термина «О большое» зависит от его области применения, но всегда растёт не быстрее, чем (точные определения приведены ниже). В частности: * фраза «сложность алгоритма есть » означает, что с увеличением параметра , характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем умноженная на некоторую константу; * фраза «функция является „о“ малым от функции в окрестности точки » означает, что с приближением к уменьшается быстрее, чем (отношение стремится к нулю).