There are \(n\) unsorted arrays: \(A_1, A_2, …, A_n\). Assume that \(n\) is…
2019
There are \(n\) unsorted arrays: \(A_1, A_2, …, A_n\). Assume that \(n\) is odd. Each of \(A_1, A_2, …, A_n\) contains \(n\) distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of \(A_1, A_2, …, A_n\) is
- A.
\(\theta (n)\) - B.
\(\theta (n \ log \ n)\) - C.
\(\theta (n^2)\) - D.
\(\theta (n^2 \ log \ n)\)
Attempted by 122 students.
Show answer & explanation
Correct answer: C
Short answer: θ(n^2).
Reasoning:
Find the median of each array.
Using a linear-time selection algorithm (median-of-medians), the median of one unsorted array of length n can be found in Θ(n) time.
Doing this for all n arrays costs n · Θ(n) = Θ(n^2).
Find the median of the n medians.
Selecting the median from these n values takes Θ(n) time.
Total cost
Θ(n^2) + Θ(n) = Θ(n^2).
Note: If one instead sorted each array, the cost would be Θ(n log n) per array and Θ(n^2 log n) overall, which is larger. The linear selection per array gives the tight worst-case bound Θ(n^2).
A video solution is available for this question — log in and enroll to watch it.