سوال ۶۱ کنکور ارشد علوم کامپیوتر ۱۴۰۳

Approach

In quicksort, the running time depends entirely on how balanced the partition is. If we can pick the median as the pivot, every partition splits the array into two halves of size $n/2$, producing the most balanced (best possible) recursion tree.

Key insight

At each recursive call on a subarray of size $m$ we do two things:

• Find the median in time $f(m)$ to use as pivot.
• Partition around that pivot in time $\Theta(m)$.

So the recurrence is:

$T(n) = 2\,T(n/2) + f(n) + \Theta(n)$

Steps

The recursion tree has depth $\log n$ (the array halves each level). At each level the total work across all nodes is bounded by the partitioning cost plus the median-finding cost. Since $f(n)$ is at least linear (finding a median requires reading all $n$ elements, so $f(n) = \Omega(n)$), at a level with subarrays of size $n/2^i$ the summed cost is dominated by terms whose total is $O(n + f(n))$ per level (the partition work sums to $\Theta(n)$ and the median work, being superadditive-bounded, sums to $O(f(n))$).

Multiplying the per-level cost by the number of levels:

$T(n) = O\big((n + f(n)) \cdot \log n\big) = O((n + f(n))\log n)$

This matches option 4.

Sanity check

If median-finding were free or linear, $f(n) = \Theta(n)$, then the bound becomes $O((n+n)\log n) = O(n \log n)$ — exactly the optimal comparison-sort bound, which is consistent. If instead $f(n)$ dominates, e.g. $f(n) = n^2$, we get $O(n^2 \log n)$, again matching the recurrence.

Pitfall: Do not multiply $n$ and $f(n)$ together (options 1 and 3). The median is found once per recursive call, not once per element. The number of recursive calls is what introduces the $\log n$ factor, and the costs $n$ (partition) and $f(n)$ (median) are added, not multiplied, at each level.