= Solution
Assume $1\leq i\leq n$. Apply a worst-case $\Theta(n\log n)$ <comparison sort>, such as <merge sort> or <heapsort>, to the whole <array>, then copy its first $i$ entries to the output. The copying costs $\Theta(i)$, so
$$
\boxed{T_1(n,i)=\Theta(n\log n+i)=\Theta(n\log n)\quad(n\geq2).}
$$
The <comparison sorting lower bound> makes the full-sort stage tight. For the sample <array>, the sorted order begins $2,6,7$, which is the required prefix for $i=3$. This method spends time ordering all $n-i$ unreported elements as well.
Back to article page
