2,460 views
3 votes
3 votes

You have an array of n  elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest lower bound for the best case performance is

a) O(n2)

b) O(nlogn)

c) Θ(nlogn)

d) O(n3)

1 Answer

Best answer
4 votes
4 votes

 best case= o(nlogn)

If we choose central element as pivot then array is divided into two equal part. And recurrence relation become T(n)=2T(n/2)+n which will take o(nlogn) time. 

Worst case  =o(n^2).

If we choose central element as pivot then array is divided into two part one part contain 0 element and other part is n-1 element.  And recurrence relation become T(n)=T(n-1)+1 which will take o(n^2).

selected by

Related questions

3 votes
3 votes
3 answers
1
Sourajit25 asked Sep 3, 2017
1,612 views
"Quick sort has good cache performance" , Can anyone explain this statement.How is cache related to quick sort.I searched for this over the internet but could not find a ...
3 votes
3 votes
1 answer
2
SHALINI PORWAL asked Aug 10, 2017
1,353 views
When array is already sorted in reverse order then what will be the recurrence relation for number of swaps on array of n elements using quick sort?
2 votes
2 votes
3 answers
3
LavTheRawkstar asked Apr 15, 2017
1,186 views
With quick sort The results after first partioning of the given array. A = (2,8,7,1,3,5,6,4,9).Analysis the time complexity of Quick sort in the best case.