Time complexity of quick sort when we take pivot as the middle element

Question

Time complexity of quick sort when we take pivot from the middle element

Answer 1

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(n²).

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)

Comments

What if the array is in sorted manner ??

Answer 2

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..

Comments

Hi @Ahwan, the youtube link u have mentioned is not working.

---

Right.

Answer 3

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?