746 views
1 votes
1 votes
What is the time complexity of quick sort when

 (i) Choosing median of sorted array as pivot.

1 Answer

Best answer
4 votes
4 votes

When we choose median as pivot , this means after applying partition the division into 2 subarrays is predefined that it will get divided into 2 halves..So recurrence relation for time will be :

          T(n)   =   2T(n/2) + O(n)  [ O(n) time is required for partition algorithm ]

==>    T(n)   =   θ(nlogn)  [ i.e. as division into subarrays is prespecified so worst case = best case = average case ]

Hence θ(nlogn) is the correct answer for the given scenario..

If however , we say central element is chosen as pivot..So it may go either at first or last or middle of array..So times will differ in that case and hence worst case will be O(n2)..

selected by

Related questions

1 votes
1 votes
1 answer
2
jugnu1337 asked Apr 20, 2022
435 views
what is T.C. of this code: for(i=1;i<=n;i++) for(j=1;j<=n;j=j+i) x=x+1;
1 votes
1 votes
1 answer
3
0 votes
0 votes
1 answer
4
iarnav asked Jun 12, 2018
839 views
Given an sorted array in descending order, what will be the time complexity to delete the minimum element from this array?