How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?

Question

The HW question, on page 362 of Data Structures and Algorithms in C++: Fourth Editionby Mark Allen Weiss, reads as follows:

Prove that merging two sorted arrays of N items requires at least 2 * N - 1 comparisons. You must show that if two elements in the merged lists are consecutive and from different lists, then they must be compared

If we are trying to find the lower bound then wouldn't the number of comparisons be N, not 2 * N - 1? If the largest element is some array Ais smaller than the smallest element in some array B then at most you would only have to do N comparisons since after all of A's elements are placed in the merged array then the remaining elements in B's can simply be appended in to the merged array.

The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2 * N - 1 seems more like it would be the upper bound since there is no way there can be more comparisons than that.

Note: I am not asking for an answer to the HW question itself as I know that is deprecated. I am confused about the implied assertion the question is making about the lower bound

Answer 1

What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound.

The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2*N* - 1 seems more like it would be the upper bound since there is no way there can be more comparisons than that.

No, it just needs to be true for some input (for infinitely many N).

For example, when we say that $\Omega(n \log n)$ is a lower bound for sorting, this does not mean that every array requires $\Omega(n\log n)$ comparisons. It just means that some arrays require that many comparisons, and thus there is no $o(n\log n)$-time algorithm for sorting.