Асимптотическая сложность влияет на производительность алгоритмов следующим образом: она определяет, насколько ухудшается работа алгоритма с усложнением поставленной задачи. 1 Алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных. 2

Например, выражение O(n^2) означает, что по мере увеличения количества входных данных время работы алгоритма (использование памяти либо другой измеряемый параметр) возрастает квадратично. 1 Если данных станет вдвое больше, производительность алгоритма замедлится приблизительно в четыре раза. 1 При увеличении количества входных данных в три раза она станет меньше в девять раз. 1

Оценка асимптотической сложности решает задачу масштабируемости данных, то есть показывает, как влияет увеличение объёма данных на увеличение времени работы алгоритма. 1