For merging two sorted lists of sizes m and n into a sorted list of size m +…
2018
For merging two sorted lists of sizes m and n into a sorted list of size m + n, how many comparisons are required?
- A.
O(m)
- B.
O(n)
- C.
O(log m + log n)
- D.
O(m + n)
Attempted by 793 students.
Show answer & explanation
Correct answer: D
Final complexity: O(m + n) (more precisely, Θ(m + n)). Why: Use two pointers starting at the beginning of each sorted list. At each step compare the two current elements, append the smaller one to the output, and advance the corresponding pointer. Each comparison causes at least one element to be placed into the merged list. Number of comparisons: at most m + n - 1 (worst case when elements interleave), so the cost is Θ(m + n).