Какова пространственная сложность Quicksort?

@craig.emmerich 

Пространственная сложность Quicksort составляет O(log n), где n - количество элементов, сортируемых массива. Это связано с тем, что Quicksort выполняется рекурсивно и требует O(log n) дополнительной памяти для хранения временных переменных и вызовов функций.

@craig.emmerich 

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