Question

There are n unsorted arrays: A₁, A₂, ..., An. Assume that n is odd. Each of A₁, A₂, ..., An 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_n is
1. O(n)
2. O(n log n)
3. O(n²)
4. Ω(n²log n)

Answer 1

Correct Answer - Option 3 : O(n²)

Total number of unsorted arrays is n and each array contain n distinct element.

Time complexity to find median from an array is O(n).

Since there is ‘n’ such array. Therefore, total time complexity to find medians of all arrays is O(n²)

Store the ‘n’ medians in an array. Find the medians of the array with time complexity of 0(n)

Total Time complexity:

T(n) = O(n²) + O(n) = O(n²)