There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements between any two arrays

Q. There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, 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 A1, A2, …, An is

(A) O(n)

(B) O(n log n)

(C) O(n²)

(D) Ω(n² log n)

Ans: Ο(n²)

Solution:

= O(n)*O(n) + O(n)

= O(n2) + O(n)

≈ O(n2)