Show that the expression \(q^2 + (n-q-1)^2\) achieves a maximum over \(q = 0, 1, \ldots, n-1\) when \(q = 0\) or \(q = n-1\).
This expression represents the sum of squares of the two subproblem sizes in quicksort’s worst-case recurrence. To find its maximum, we’ll use calculus to analyze the function’s behavior.
Consider \(f(q) = q^2 + (n-q-1)^2\) as a continuous function of \(q\) over the interval \([0, n-1]\). We’ll find the critical points by taking the derivative and setting it to zero.
First derivative:
\[\begin{align*} f'(q) &= \frac{d}{dq}\left[q^2 + (n-q-1)^2\right] \\ &= 2q + 2(n-q-1) \cdot (-1) \\ &= 2q - 2(n-q-1) \\ &= 2q - 2n + 2q + 2 \\ &= 4q - 2n + 2 \end{align*}\]Setting \(f'(q) = 0\):
\[\begin{align*} 4q - 2n + 2 &= 0 \\ 4q &= 2n - 2 \\ q &= \frac{n-1}{2} \end{align*}\]So the critical point is at \(q = (n-1)/2\), which is the midpoint of the interval.
Taking the second derivative:
\[f''(q) = \frac{d}{dq}[4q - 2n + 2] = 4\]Since \(f''(q) = 4 > 0\) for all \(q\), the function is convex (concave up). This means the critical point at \(q = (n-1)/2\) is a minimum, not a maximum.
For a convex function on a closed interval, the maximum must occur at one of the endpoints.
At \(q = 0\):
\[f(0) = 0^2 + (n-0-1)^2 = (n-1)^2\]At \(q = n-1\):
\[f(n-1) = (n-1)^2 + (n-(n-1)-1)^2 = (n-1)^2 + 0^2 = (n-1)^2\]Both endpoints give the same value \((n-1)^2\), which is the maximum.
For integer values of \(q\) in \(\{0, 1, \ldots, n-1\}\), the function achieves its minimum near the middle and increases as we move toward either endpoint. The maximum is achieved at both extreme values \(q = 0\) and \(q = n-1\).
These correspond to the most unbalanced partitions in quicksort: one subproblem of size \(n-1\) and one of size 0.
Visualization
Here is a neat visualization in Desmos. Head over there to play with the variables.
As you can see, the equation has two maximum values, one on the leftmost side (\(q = 0\)) and one on the rightmost side (\(q = n - 1\)).