Худший случай быстрой сортировки - это когда вы выбираете элемент pivot, который является минимальным или максимальным элементом из массива, так что все оставшиеся элементы переходят на одну сторону раздела, а другая сторона раздела пуста. В этом случае непустое разбиение имеет размер (n - 1), и для линейного разбиения требуется линейное время (kn для некоторой константы k> 0), поэтому рекуррентное соотношение равно
T (n) = T (n - 1) + T (0) + kn
Если мы предположим, что T (n) = an² + bn + c для некоторых констант a, b, c, тогда мы можем заменить:
an² + bn + c = [a (n - 1) ² + b (n - 1) + c] + [c] + kn
, где два члена в квадратных скобках - это T (n - 1) и T (0) соответственно. Расширяя скобки и приравнивая коэффициенты, мы получаем
an² = an²
bn = -2an + bn + kn
c = a - b + 2c
Отсюда следует, что существует семейство решений, параметризованных c = T (0), где a = k / 2 и b = k / 2 + c. Это семейство решений может быть записано точно как
T (n) = (k / 2) n² + (k / 2 + c) n + c
, чтоэто не просто O (n²), но Ө (n²), что означает, что время выполнения является квадратичной функцией, а не просто ограничено сверху квадратичной функцией. Обратите внимание, что фактическое значение c не меняет асимптотическое поведение функции, если k> 0 (т. Е. Шаг разделения занимает положительное время).