Suppose there are log log n sorted lists, each containing elements. What is…
Suppose there are log log n sorted lists, each containing
elements.
What is the time complexity of producing one fully sorted list containing all elements?
Answer: D. O(n2 log(log logn)) — Key facts: There are log log n sorted lists, each of size n^2 / log log n (from the given image). Step 1: Compute the total number of elements. Total N = (log…
- A.
O(n2)
- B.
O(n2 log logn)
- C.
O(n2 log logn / loglogn)
- D.
O(n2 log(log logn))
Attempted by 275 students.
Show answer & explanation
Correct answer: D
Key facts: There are log log n sorted lists, each of size n^2 / log log n (from the given image).
Step 1: Compute the total number of elements. Total N = (log log n) × (n^2 / log log n) = n^2.
Step 2: Use an optimal merge method. Merging k sorted lists with total N elements using a min-heap (or priority queue) takes O(N log k) time.
Step 3: Substitute k = log log n. Then log k = log(log log n), so the merge cost is O(N log k) = O(n^2 log(log log n)).
Therefore, the time complexity of producing one fully sorted list containing all elements is O(n^2 log(log log n)).
Remark: Pairwise repeated merging without a heap would be less efficient; the min-heap approach gives the stated bound directly.
A video solution is available for this question — log in and enroll to watch it.