Algorithms Analysis Practice Test 2025 - Free Algorithms Practice Questions and Study Guide

In the average case for QuickSort, the space complexity is determined primarily by the recursion stack during the sorting process. QuickSort works by selecting a "pivot" element and partitioning the array into two halves, which are then sorted independently.

In the average case, the pivot usually divides the array into two roughly equal parts. This results in a logarithmic depth of recursion, as each recursive call handles part of the array. Specifically, for an array of size n, you could expect about log(n) levels of recursive calls (assuming balanced partitions).

At each level of recursion, space is used on the stack for managing function calls. Since the maximum depth of the recursion stack corresponds to the logarithm of the size of the input data, the average space complexity for QuickSort is O(log n).

This understanding is based on the method of partitioning and the nature of recursive function calls in QuickSort, which permits efficient use of stack space while sorting. The other options reflect either incorrect assessments of recursion depth or total space usage through other interpretations, which do not apply to the average case behavior of QuickSort.