Для примера возьмем быструю сортировку . Каждый последующий рекурсивный вызов n быстрой сортировки имеет сложность времени выполнения T (n)
T (n) = O (n) + 2 T [(n-1) / 2]
в «лучшем случае», если несортированный входной список разбивается на два равных подсписка размера (n-1) / 2 в каждом вызове. Решение для T (n) дает O (n log n), в этом случае. Если раздел не идеален и два подсписка не имеют одинаковый размер n, то есть
T (n) = O (n) + T (k) + T (n - 1 - k),
мы все равно получаем O (n log n), даже если k = 1, только с большим постоянным фактором. Это связано с тем, что количество рекурсивных вызовов быстрой сортировки растет экспоненциально при обработке списка ввода, пока k> 0.
Однако в «наихудшем случае» деление входного списка не происходит, т. Е .:
T (n) = O (n) + T (0) + T (n - 1) = O (n) + O (n-1) + T (n-1) + T (n-2) ....
Это происходит, например, если мы возьмем первый элемент отсортированного списка в качестве элемента сводки.
Здесь T (0) означает, что один из результирующих подсписков равен нулю и, следовательно, не занимает вычислительное время (поскольку подсписок имеет нулевые элементы). Вся оставшаяся нагрузка T (n-1) необходима для второго подсписка. В этом случае мы получаем O (n²).
Если бы алгоритм не имел худшего сценария, он был бы не только O [f (n)], но и o [f (n)] (Big-O против little-o нотации ).