The Gateway to Computer Science Excellence
0 votes

In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexity of quick sort.

  1. O($n^2$)
  2. O($n^3$)
  3. O(nlogn)
  4. O(n)
in Algorithms by Boss | 491 views
It will be O(n²).
in worst case it must be 0(n^2)


what is ans??

I think even sorting not possible, in this case.


@Verma Ashish

how ? 

What i think is-

There is no need to select 75th greatest element as pivot.. because its its searching itself takes O(n²) time..

Whatever pivot is selected quick sort worst case O(n^2).

Whatever pivot is selected quick sort worst case O(n^2)

but here it is given that this procedure takes $O(n^2)$ time and in original quick sort, it takes O(1) time because we go to that index in array and select it and then do the partition procedure. Here, I think, we have to include $O(n^2)$ in recurrence.

So, recurrence will look like $T(n) = T(74) +T(n-75) + O(n^2) + O(n)$

O(n^2) to select pivot then partition will take O(n) time and after partition, 74 elements which are right of 75th greatest elements will be more than 75th greatest element and elements on left side will be less than that 75th greatest element. Now here T(74) will be constant(c) and now we have to solve recurrence to find running time.

please correct me if I am wrong.

Yes, answer is O($n^2$).

But I am not getting why recurrence relation is different if 75th minimum element is selected as pivot is given.

@sresthaHow sorting is not possible???

It is possible I think???




it will lead to $O(n^3)$  right?

Whatever pivot is selected quick sort worst case O(n^2).

​​​​​​​​​​​That was unconsciously written..

 We can chose first or last element as pivot..$T(n)=T(n-1)+T(0)+O(n)=O(n^2)$


@Verma Ashish

yeah, it seems to $O(n^3)$ but I didn't solve it.


please post the given solution.

If a list contain only 10 element, then how can it be sorted, with this algo??

3 Answers

+1 vote

Generally PARTITION process take O(n) time complexity in quick sort.

But here, IMPROVED-PARTITION process take $O(n^2)$ time complexity.


quickSort(array, leftmostIndex, rightmostIndex)
  if (leftmostIndex < rightmostIndex)
    pivotIndex <- improved-partition(array,leftmostIndex, rightmostIndex)
    quickSort(array, leftmostIndex, pivotIndex)
    quickSort(array, pivotIndex + 1, rightmostIndex)

The worst case occurs when the partition process always picks greatest or smallest element as pivot. If we consider above partition strategy where  75th greatest Element is selected as pivot, the worst case would occur when the array is already sorted in increasing or decreasing order.

T(n) = T(n-1) + O($n^2$)

The solution of the above recurrence by substitution method is O($n^3$).

Solution :

by Active
0 votes
n^3 is true but any one can explain it.
0 votes
Option (2): O(n^2)

The time complexity in worst case for quick sort is O(n^2)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,222 questions
59,851 answers
118,095 users