Suppose there are ⌈ log n ⌉ sorted lists of ⌊ n/log n ⌋ elements each. The…
2005
Suppose there are ⌈ log n ⌉ sorted lists of ⌊ n/log n ⌋ elements each. The time complexity of producing a sorted list of all these elements is
- A.
O(n log log n)
- B.
θ(n log n)
- C.
Ω(n log n)
- D.
Ω(n3/2)
Attempted by 363 students.
Show answer & explanation
Correct answer: A
Final complexity: O(n log log n)
Reasoning:
Number of sorted lists k = ⌈log n⌉, each with about n/ log n elements, so the total number of elements is n (up to rounding).
Use a min-heap (priority queue) of size k to merge the k sorted lists: initially insert the first element of each list into the heap, then repeat n times extracting the smallest element and inserting the next element from the list it came from.
Each heap operation (extract or insert) costs O(log k). There are O(n) such operations overall, so the total time is O(n log k).
Since k = ⌈log n⌉, log k = log log n, giving O(n log log n).
Hence the time complexity of producing a single sorted list of all elements is O(n log log n).