There are n unsorted arrays A1, A2, …, An. (Assume that n is odd.) Each of A1,…
2021
There are n unsorted arrays A1, A2, …, An. (Assume that n is odd.)
Each of A1, A2, …, An contains n distinct elements, and no element is common to any two arrays.
The worst-case time complexity of computing the median of the medians of A1, A2, …, An is
Answer: C. O(n2) — Concept Finding the median of n elements is a selection problem, not a sorting problem. The median-of-medians algorithm (Blum–Floyd–Pratt–Rivest–Tarjan)…
- A.
O(n)
- B.
O(n log n)
- C.
O(n2)
- D.
O(n2/log n)
- E.
Question not attempted
Attempted by 443 students.
Show answer & explanation
Correct answer: C
Concept
Finding the median of n elements is a selection problem, not a sorting problem. The median-of-medians algorithm (Blum–Floyd–Pratt–Rivest–Tarjan) returns any order statistic of n elements in Θ(n) time even in the worst case, whereas no comparison-based sort can beat the Ω(n log n) lower bound that sorting is subject to. And when a computation runs in phases, its total cost is the sum of the phase costs, a sum that is always dominated by its largest term.
Applying it here
One array. Each Ai holds n elements, so its median is a single selection on n elements: Θ(n) in the worst case. Sorting Ai first would cost n log n, but a sort is never needed to read off one order statistic.
All n arrays. There are n arrays and they share no elements, so no work carries over from one to the next: n × Θ(n) = Θ(n2) to produce all n medians.
The medians themselves. Those n medians form one new array of n elements. Its median is one more selection on n elements: Θ(n).
Total. Θ(n2) + Θ(n) = Θ(n2), since the quadratic term dominates the linear one. The worst-case time complexity is therefore O(n2).
Cross-check
Can it be done faster? No — and the reason is specific to this problem, not a general appeal to input size. Suppose an algorithm answered without ever inspecting some element x of Ai. An adversary may fill the other arrays so that Ai's median is exactly the median of the medians, and then move x so that Ai's median shifts to a neighbouring value; the answer already committed to is then wrong. So every one of the n2 elements must be read, Ω(n2) work is unavoidable, and the task cannot be brought down to O(n), O(n log n) or O(n2/log n). The selection-based procedure above meets that floor exactly.
Why not n^2^ log n? Sorting each array and reading its middle element gives n × n log n = n2 log n. That is the price of an unnecessary sort, not the cost of the task: selection is strictly cheaper than sorting, so n2 log n is the running time of a wasteful method rather than the worst-case complexity of the problem.