Сложность алгоритма
Количество шагов, необходимых для выполнения алгоритма, выраженное через размер входных данных.
Асимптотическая сложность
Функция, описывающая зависимость времени выполнения алгоритма от размера входных данных. Обычно выражается в Big O-нотации.
Big O-нотация
О-большое обозначение, используемое для описания верхней границы сложности алгоритма в худшем случае.
О-большое ($O(f(n))$)
Функция, которая растет не быстрее, чем $f(n)$, при $n$ стремящемся к бесконечности. Используется для оценки верхней границы сложности.
О-малое ($o(f(n))$)
Функция, растущая не медленнее, чем $f(n)$, при $n$ стремящемся к бесконечности. Используется для оценки нижней границы сложности.
Theta-нотация ($\Theta(f(n))$)
Функция, растущая с той же скоростью, что и $f(n)$, при $n$ стремящемся к бесконечности. Используется для точного описания сложности.