Почему для завершения каждого уровня стека вызовов в быстрой сортировке требуется O (n) времени?

Question

Я нашел это объяснение быстрой сортировки в Интернете:

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

Answer 1

Временная сложность O (n) игнорирует постоянные факторы. Этот оператор обрабатывает каждое разбиение как дробную константу исходных n элементов. Идеальное разделение было бы примерно 50% и 50%, за исключением того, что схемы типа Ломуто не включают элемент поворота при рекурсивных вызовах. Таким образом, в случае, когда самый глубокий слой дает 2 элемента, постоянный коэффициент для O (n) будет 2 / n (поскольку (2 / n) (n) == 2).