###### Question 7788 – Algorithms

November 10, 2023###### NTA UGC NET JUNE-2023 Paper-2

November 10, 2023# Question 7812 – Algorithms

There are n unsorted arrays: A_{1}, A_{2}, …, A_{n}. Assume that n is odd. Each of A_{1}, A_{2}, …, 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}, …, A_{n} 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(n

They are clearly saying that all are distinct elements.

There is no common elements between any two arrays.

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(n

^{2})**Note:**They are clearly saying that all are distinct elements.

There is no common elements between any two arrays.

O(n)

O(n log n)

Ω(n

^{2}log n)O(n

^{2}) Subscribe

Login

0 Comments