GATE CSE 2014 | Set 3 | Question: 14

Question

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

• A. $O(n^2)$
• B. $O(n \log n)$
• C. $\Theta(n\log n)$
• D. $O(n^3)$

Comments

NOTE: Central or middle $\neq$ Median

It may so happen that every time you choose the central element and that central element is either largest or smallest, this is the worst case scenario. Hence, $\Theta (n^2)$ time.

Median = A number which has n/2 elements lesser than or equal to and n/2 elements are greater than or equal to it.

If each time MEDIAN is chosen, then it is the best or avg case of quick sort, so in this case, time complexity will be $\Theta (nlogn)$

See below question:

https://gateoverflow.in/1830/gate-cse-2006-question-52

---

I thought the same thing at the moment i saw the question. later saw your comment on median != central.
Thanks for answer

---

The central element is simply  midpoint of an array based on index position, whereas the median is the middle value of a sorted dataset that splits it into two equal halves

Answer 1

Correct Option: A – $O(n^2)$.

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

Comments

Arjun Sir’s comment, I’m not getting this line clearly.

 

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

 is this means the other case in sorted array like if we take 7 in above sequence?? then also we get 1 and n-1 partitions of pivot.

please anyone correct if I’m wrong...

---

central element not means it is median even if at central element there may exist smallest or largest element so worst case time complexity dont change.

---

What i can summarize is

For every fixed position of pivot element in quick sort algo their exists an order of elements in array that would lead to worst behaviour of O(n^2).

Answer 2

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

 

Comments

goat brooo

 

Answer 3

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.

Comments

When All n Element are identical then complexcity  will be O(n^2).

---

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)

---

Please add a feature to remove answers with incorrect reasons, they do more harm than good.

Answer 4

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.

Answer 5

The tightest upper bound for the worst case performance of quicksort when always choosing the central element of the array as the pivot is O(n^2).

This is because if the input array is already sorted or if the array is sorted in the reverse order and the pivot is always the central element, the partition will always result in one side having n-1 elements and the other side having 0 elements, leading to a worst-case scenario where each partition takes O(n) time and the overall quicksort takes O(n^2) time.

It's important to note that this is an worst-case scenario, and in practice, the average case performance of quicksort is O(n*log(n)) which makes it a good choice for sorting large data sets in most cases.

Also, this worst case is not so likely to happen if the pivot is chosen randomly, rather than always using the central element as pivot.

Answer 6

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.

Comments

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