Project ForgeThere 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
- AO(n)
- BO(n log n)
- O(n²)
- DΩ(n² log n)
Explanation
Finding the median of each individual n-element array takes O(n) time using a linear-time selection algorithm, and this must be done for all n arrays, costing O(n) × n = O(n²) total. Then finding the median of the resulting n medians takes a further O(n) using the same selection technique. The O(n²) term from computing all n individual medians dominates, giving an overall worst-case time complexity of O(n²).
Source: GATE CS 2019 (Set-2) (2019)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.