Худший случай сложности
В информатике (особенно в теории сложности вычислений), худший случай сложности (он обозначается Big-oh(n)) измеряет ресурсы (например, время выполнения, память), которые требуются алгоритму для обработки входных данных случайного размера (обычно обозначаемого  в асимптотическом обозначении). Он обозначает верхнюю границу ресурсов, требуемых алгоритму.

В случае со временем выполнения, худший случай временной сложности алгоритма обозначает самое долгое время выполнения требуемое алгоритму для обработки любого размера входных данных , тем самым гарантируя, что алгоритм выполнится в обозначенный период времени. Порядок роста (например, линейный, логарифмический) худшего случая сложности обычно используется для сравнения эффективности двух алгоритмов.

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

Определение 

Дана модель вычислений и алгоритм , который останавливается на каждом входе , соответствие  называется временной сложностью алгоритма  если, для каждой входной строки ,  останавливается точно после  шагов.

Так как нас обычно интересует зависимость временной сложности алгоритма на входных данных различной длины, злоупотребляя терминологий, временной сложностью алгоритма иногда называют соответствие , определяемое максимальной сложностью 

входных данных  длиной или размером .

Подобные определения могут быть даны пространственной сложности.

Способы формулировки 

Очень часто, сложность  алгоритма  дана в асимптотическом Big-O обозначении, которое обозначает его рост в форме  с функцией сравнения использующей конкретные вещественные значения  и обозначением:
 Существует позитивное вещественное число  и натуральное число  такие, что

Довольно часто, формулировка звучит следующим образом:
 „Алгоритм  имеет худший случай сложности .“
или еще короче:
 „Алгоритм  имеет сложность .“

Примеры 
Рассмотрим выполнение алгоритма сортировки вставками на  числах с использованием машины с произвольным доступом к памяти. В лучшем случае для алгоритма, когда числа уже отсортированы, требуется  шагов для выполнения задачи. Однако, в худшем случае для алгоритма, когда числа отсортированы в обратном порядке, требуется  шагов для их сортировки; таким образом худший случай временной сложности алгоритма сортировки вставками .

См. также 
 Теория алгоритмов

Ссылки 
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 2.2: Analyzing algorithms, pp.25-27.
 Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. , p.32.

Анализ алгоритмов