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

Approach

We must merge $i$ already-sorted lists whose sizes sum to $n$ total elements, and decide for which values of $i$ the merge is achievable in $O(n)$ time.

Key insight

A $k$-way merge of $i$ sorted lists with $n$ total elements can be done in $\Theta(n \log i)$ comparisons using a min-heap of size $i$: each of the $n$ output elements costs one $O(\log i)$ extract-min plus one $O(\log i)$ insert. So the cost depends on $i$:

• If $i$ is a constant $c$, then $\Theta(n \log c) = \Theta(n) = O(n)$.
• If $i$ grows with $n$ (e.g. $i = n$ with each list of size $1$), merging becomes equivalent to fully sorting $n$ elements, which needs $\Omega(n \log n)$ in the comparison model — strictly worse than $O(n)$.

Evaluating the options

1. "Only for $i=2$": false. $i=2$ gives $O(n)$, but so does any other constant $i$ (e.g. $i=3$). The word "only" is wrong.
2. "For any arbitrary $i$": false. If $i$ is allowed to scale with $n$, the merge degenerates into a comparison sort needing $\Omega(n \log i)$, which is not $O(n)$.
3. "For $i > 2$, $\Omega(n \log n)$": false. For a constant $i > 2$ the merge is $O(n)$, not $\Omega(n \log n)$; the blanket lower bound is incorrect.
4. "Only for any constant $i$, $O(n)$": correct. $O(n)$ is exactly achievable when (and only when) $i$ is a constant, since then $\log i$ is a constant factor.

Sanity check

Set $i=n$, all singleton lists: a correct $O(n)$ merge would sort $n$ arbitrary keys in linear comparisons, contradicting the $\Omega(n \log n)$ comparison-sort lower bound. This rules out options 1 and 2 and confirms the constant-$i$ restriction in option 4.

Pitfall: Do not assume two-way merge ($i=2$) is the special boundary. The real boundary is "$i$ constant vs. $i$ growing": every fixed $i$ works in $O(n)$ because $\log i$ collapses to a constant factor, while a growing $i$ reintroduces the $\log$ factor of sorting.