GATE 2019 CS – Question 47

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

There are $n$ unsorted arrays: $A_1,A_2,\dots,A_n$. Assume that $n$ is odd. Each of $A_1,A_2,\dots,A_n$ 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_1,A_2,\dots,A_n$ is

$O(n)$
$O(n\log n)$
$O(n^2)$
$\Omega(n^2\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $O(n^2)$

Explanation

The median of each array is found in $O(n)$ time (median of medians selection), so the $n$ arrays take $O(n^2)$ in total. The median of the resulting $n$ medians takes another $O(n)$, so the total is $O(n^2)$.