GATE 2019

Question

What is the complexity of finding median of medians of N lists containing N elements each.

N is odd and the lists are unsorted and no 2 lists have same element.

Comments

O(n^2)

Answer 1

O(n^2)

As per the options, as they were all in Big O, so I took worst i.e. O(n^2)

Comments

To sort : n log n

And for n such arrays n * n log n

i.e n^2 log n

---

I think is O(N^2) because apply n times selection procedure as median is (n+1)/2 (given that n is odd) so we get n medians of median now again aplply selection procedure so O(N) so net time complexity is O(N^2) correct me if i am wrong

---

@Aman lists are unsorted..

---

Selection algorithm is for unsorted lists. It is randomised algorithm and takes O(n) time to find k'th smallest element. Specifically for this case, k=(n+1)/2.

Answer 2

Median can be found in O(n) using randomised partition for 1 list.

For n lists it is n*n, so I think O(n^2) is the answer.

Comments

but isnt it like if O() is asked then always the max among the options?

---

No, that is not required.

Generally we take the tightest upper bound. Theoretically O(n^2) is subset of O(n^2log n).

---

So what should be the final answer as per you? @xariniov9

coz n2logn looks correct for sure.