In which of the following cases does the worst-case time complexity of Quick…

CONCEPT: Quick Sort's running time depends on how evenly the pivot partitions the current subarray. Balanced partitions keep the recursion depth logarithmic, while repeatedly one-sided partitions make the recursion depth linear.

When each partition removes only the pivot and leaves all remaining elements on one side, the recurrence is T(n) = T(n - 1) + O(n), which sums to O(n2).

APPLICATION: Apply that rule to the cases in this item:

1. If the pivot is the smallest or largest element, one side of the partition is empty and the other side has n - 1 elements.

2. If the same kind of pivot is chosen again, the next subproblem has n - 2 elements, then n - 3 elements, and so on.

3. The partition work across levels is n + (n - 1) + (n - 2) + ... + 1 = O(n2), so this is the worst-case time complexity pattern.

CROSS-CHECK / CONTRAST:

• Random pivot selection is meant to make repeated extreme pivots unlikely; it does not define the worst-case condition.

• An already sorted array is a worst case only for pivot rules such as always selecting the first or last element; sortedness is not the deeper cause.

• Rejecting all choices is inconsistent because an extreme pivot does create the unbalanced partition chain.

Result: The condition that captures the worst case is that the pivot element is the smallest or largest element.