Question: Consider the algorithm we outlined in class for merging two lists. In the worst case, how many element comparisons will this algorithm take to merge an array with n elements and an array of m elements? The answer should be exact; do not use big-O or Theta notation to approximate.
Answer: After each comparison, we place exactly one element into the resulting array. There will be m+n elements in this array, so we can have a bound of m+n.
We can write a slightly stronger bound by observing that once one of the arrays is empty we do no more comparisons. In the worst case, at this point the non-empty array will have only one element left. So this removes one comparison, to get m+n-1.