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

Question

Я изучаю алгоритм и хотел бы получить помощь по следующему вопросу:

Какова временная сложность алгоритма быстрой сортировки в массиве [k+1, ..., n, 1, ..., k], где k > n/2, а ось всегда выбирается самой правой ячейкой подмассива?

Будет ли это O(n²) или O(n log n)?

Из отсканированного теста алгоритмов из прошлого семестра студент сказал O(n²) (с чем я согласился после нескольких симуляций), но этот студент получил неправильный ответ без объяснений. Я и пара других студентов не понимаем, почему ответ помечен как неправильный, когда мы все трое пришли к одному и тому же выводу.

Answer 1

O (n²) является правильным.

При первом проходе в качестве точки поворота будет выбран самый правый элемент k, который разделит остальную часть массива на [1, ..., k-1] слева и [k+1, ..., n] справа. Поскольку оба этих подмассива расположены в отсортированном порядке, они имеют форму, в которой быстрая сортировка выбирает крайний правый элемент, поскольку ось сводится к квадратичному c разу.

Поэтому для сортировки левой части раздела потребуется O (k²) время, и сортировка правой стороны займет O ((nk) ²) время. Поскольку у нас есть n/2 < k <= n, у нас также есть O (k²) = O (n²).