1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

# The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which remains is selected as pivot?

A
Θ(n)
No worries! Weâ€˜ve got your back. Try BYJUâ€˜S free classes today!
B
Θ(n3)
No worries! Weâ€˜ve got your back. Try BYJUâ€˜S free classes today!
C
Θ(n2)
No worries! Weâ€˜ve got your back. Try BYJUâ€˜S free classes today!
D
Θ(n log n)
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
Open in App
Solution

## The correct option is D Θ(n log n)If the median of n elements can be found in 0(n) time and we select the median as pivot. Then quicksort sort n elements of an array A[1],...A[n] as follows. We permute the elements in the array so that for same j all the records with key less than v appear in A[1] ,...A[j] and all those with keys v or greater appear in A[j + 1] ,....A[n]. We then apply quicksort recursively to A[1],...,A[j] and to A[j + 1] ,...,A[n]. The recursion equation becomes for some valus of i T(n)≤1n∑ni=i(T(i−1)+T(n−1) The solution of the T(n)≤Θ ( n log n) Given to find median 0(n) time required.

Suggest Corrections
0
Join BYJU'S Learning Program
Related Videos
Median
MATHEMATICS
Watch in App
Explore more
Join BYJU'S Learning Program