7.9k views

You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

1. $O(n^2)$
2. $O(n \log n)$
3. $\Theta(n\log n)$
4. $O(n^3)$
edited | 7.9k views
+7

Important word 'central element'. It may not be median. Hehe

+2

Yes right. For a sorted array only median lies in the central position. For unsorted array median may not be there in the middle.

0

What is the difference between the above question and this https://gateoverflow.in/25209/tifr2012-b-14 ?

(A) $O(n^2)$ is the answer. When we choose the first element as the pivot, the worst case of quick sort comes if the input is sorted- either in ascending or descending order. Now, when we choose the middle element as pivot, sorted input no longer gives worst case behavior. But, there will be some permutation of the input numbers which will be giving the same worst case behavior. For example,

$1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7$
This array gives worst case behavior for quick sort when the first element is pivot.

$6 \ 4 \ 2 \ 1 \ 3 \ 5 \ 7$
This array gives the worst case behavior of $O(n^2)$ if we take middle element as the pivot- each split will be $1$ element on one side and $n-1$ elements on other side. Similarly, for any input, we can have a permutation where the behavior is like this. So, whichever element we take as pivot it gives worst case complexity of $O(n^2)$ as long as pivot is from a fixed position (not random position as in randomized quick sort).

edited by
0

sir can u please tell me how this order works ....(i.e) 6 4 2 1 3 5 7... ???....

if the input is...... 5 5 5 5 5 5 5 ....then i think it will be O(n^2)....

0
Sir I didn't understand the explanation What I have got is that If array is sorted and if we choose first or last element as pivot then complexity will be O(n^2) and if we chose central element as pivot then we'll get complexity as O(n log n) .But if array is unsorted and then we pick central element as pivot then complexity will be O(n^2) How?????

Also what is the difference between median pivot or central element as pivot?
+10

What I have got is that If array is sorted and if we choose first or last element as pivot then complexity will be O(n^2)

Yes.

if we chose central element as pivot then we'll get complexity as O(n log n)

By central element if you mean in the sorted array then this is correct. In a random array even if we select the central element as pivot, it can cause worst case of $O(n^2).$

0

Sir, did not understand 2nd part- here how we are always choosing middle element as pivote. ??

If we have to sort this list using quick, then we need to proceed as -
6 4 2 1 3 5 7   // here pivote index = 5 (starting with 1)

5 4 2 1 3 6 7   // pivote index = 4

3 4 2 1 5 6 7

3 1 2 4 5 6 7  // pivote = 3

2 1 3 4 5 6 7  // pivote = 2

1 2 3 4 5 6 7

here in all case - quick sort divides the list in two parts where left side list has n-1 elements and right side part has 1 element, so time complexity is O(n2) .

Is this correct sir  ??

But I did not understand here that how we will take middle element as pivote..

+1

And how this question is different from https://gateoverflow.in/1830/gate2006_52

+2
vijya middle means mid of array . but meadian means mid of sorted array.
0
@Anirudh , thanks , but now lets talk about this question. Can you please explain the example given by arjun sir in the 2nd part ??

I mean  A = 6 4 2 1 3 5 7.

How do we always get middle element as pivote here while doing quick sort  ??
+3
it is not working of given example , since mid is 1 so partition will be ,
1 (426357)
here midd is 6
1 (2435) , 6 (7)
like this
but u take example 66666666
or think like this every think u pic midd element which partition array into n-1 left or right element .
+2
Pivot means a element in which all the left portion of this pivot will be less than this and all the right portion of this pivot will be greater than this so here if the array is not in increasing or decrasing order if we take median element as a pivot it can happen that it is the smallest element of the whole array that we are taking as pivot so therefore taking this as the middle element all the rest elements are in the RHS portion and no elemens in LHS so partion in 1 and (n-1) portins so complexity O(n^2).
0
then what will be the best case ?as we know choosing the central element gives best case of the quick sort .will it depends upon the permutation of the element ??
0
@rajesh raj it will be best case for any given array but not fot random array....
0
What a nice point Arjun sir
0

So, whichever element we take as pivot it gives worst case complexity of O(n2) as long as pivot is from a fixed position

https://gateoverflow.in/1325/gate2009-39

0
what is the recurrence relation for the above problem??
0
Also, $O(n^3)$ is an upper bound, surely it's not a tight bound.

You already know that when choosing the first or last element as pivot, quick sort gives worst case complexity in ascending/descending order. It also gives worst case O(n2) when all elements are same.

Simply, check for all these cases first.

So, in ascending/descending order, choosing mid element as pivot gives O(nlogn) but choosing all elements same such as [2 2 2 2 2] still gives O(n2).

+1 vote
A.

The Worst case time complexity of quick sort is O (n^2). This will happen when the elements
of the input array are already in order (ascending or descending), irrespective of position of
pivot element in array.
+3
The reason given is not correct. When input is in order, choosing the middle element as pivot gives the best case of $O(n \log n)$.
+1
If you choose not middle element but median as pivot element each time then complexity will come down to nlogn in worst case..
0
Sir shouldn't it be theta(nlogn ) rather that O(nlogn) for the best case when input is in order.
+1
When All n Element are identical then complexcity  will be O(n^2).
+3
if you take center or median as a pivot element then  also  worst case complexity will be O(n^2) because if you take all  elements same  then no effect of taking median it will take O(n^2) but you can say that all elements are distinct and you take the pivot as median then it will be O(nlog n)
+1 vote
when we select the central element as pivot element then the worst case time complexity will be O(nlogn).You may get doubt why not always choose mid element as pivot,this is because although this produceses O(nlogn) time complexity when we compute the constant time also then this will be more than selecting other elements as pivot.
0

@admin when we choose central element as pivot then T.c will be O(nlogn) assumed that array is sorted in ascending or descending order but if the array is unsorted then every time in worst case that central element can go into extreme position (left or right) & cause T.C O(n^2).

I think the simplest way to solve this question is if we consider an array of n elements where all the elements are the same since it is not mentioned in the question that the elements need to be distinct. In this case Quick Sort will take $O(n^{2})$ time. Therefore the option will be A.

1
2