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(n2)
(D) Ω(n2 log n)
Ans: Ο(n2)
Solution:
= O(n)*O(n) + O(n)
= O(n2) + O(n)
≈ O(n2)