There are n unsorted arrays: A₁, A₂, …, Aₙ. (Assume that n is odd) Each of A₁,…
2021
There are n unsorted arrays:
A₁, A₂, …, Aₙ. (Assume that n is odd)
Each of A₁, A₂, …, Aₙ 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₁, A₂, …, Aₙ is
- A.
O(n)
- B.
O(nlogn)
- C.
O(n2)
- D.
O(n2/logn)
- E.
Question not attempted
Attempted by 287 students.
Show answer & explanation
Correct answer: C
To compute the median of the medians of n arrays, each of size n: Step 1: For each array Aᵢ, find its median. Since each array has n elements, this can be done in O(n) time using the selection algorithm. Step 2: There are n arrays, so computing all n medians takes O(n × n) = O(n²) time. Step 3: The medians form a new array of size n. Finding the median of this array takes O(n) time. Step 4: Total time complexity is O(n²) + O(n) = O(n²). Thus, the worst-case time complexity is O(n²).