retagged by
7,584 views

3 Answers

7 votes
7 votes

Since you are taking middle element as pivot which means we have elements in unsorted manner.

In worst case if this middle element is placed at starting or ending of list after partition procedure.

then recursive equation will be like T(n)=T(n-1)+o(n)  which result in time complexity as o(n2).

In best case if the element place at exactly between the list which divides the list in exactly half's after the partition procedure.

then recursive equation be like T(n)=2T(n/2)+o(n) which results in time complexity as o(nlogn)

NOTE:If you have taken the median as pivot which ensures that elements is in ascending order then time complexity will always be o(nlogn)

5 votes
5 votes
Many people misunderstand it for the first time.
They think if you choose last element then it is dividing the problem in to subproblems  of size  n-1  & 0 always & when you select middle one as pivot, it will always divide it in to two equal subproblems.

No,  in Partition algorithm,  that index will be returned which the right place for the pivot. That decides the way it is devided.

5 2 3 9 4 6 1
Suppose you select middle element as pivot.  So  9 as pivot.
At the end of partition,   9 will be at it's right position. i.e last index of array.....
So the problem is divided in to subproblems of size   n-1 & 0....    
This is the worst case.   O(n ^2)

When best case happens ?
After partition algorithm, if pivot goes to middle index then it divides the problem in to subproblems of size n/2 each. So best case happens.

So it depends on where the pivot goes after partition algorithm, not which element you choose.

Again, it is not about only one partition call.... Partition will be called many times too..
edited by
0 votes
0 votes
applying partitioning algorithm will take O(n) while sorting function will take 2T(n/2)

total time complexity = 2T(n/2)+o(n) =Θ(nlogn),  is it correct?

Related questions

4 votes
4 votes
1 answer
1
akankshay asked Mar 9, 2016
15,735 views
the worst case time complexity of quicksort for an elements when the median is selected as the pivota. o(n^2)b.o(n)c.o(nlogn)d.o(logn)
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.
3 votes
3 votes
2 answers
4