...
Question 7788 – Algorithms
November 10, 2023
NTA UGC NET JUNE-2023 Paper-2
November 10, 2023
Question 7788 – Algorithms
November 10, 2023
NTA UGC NET JUNE-2023 Paper-2
November 10, 2023

Question 7812 – Algorithms

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

Correct Answer: D

Question 3 Explanation: 
Finding the median in an unsorted array is O(n).
But it is similar to quicksort but in quicksort, partitioning will take extra time.

→ Find the median will be (i+j)/2
1. If n is odd, the value is Ceil((i+j)/2)
2. If n is even, the value is floor((i+j)/2)
-> Here, total number of arrays are
⇒ O(n)*O(n)
⇒ O(n2)

Note:
They are clearly saying that all are distinct elements.
There is no common elements between any two arrays.
A
O(n)
B
O(n log n)
C
Ω(n2 log n)
D
O(n2)
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!