The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 votes

Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting $n$ ( $\geq $ 2) numbers? In the recurrence equations given in the options below, $c$ is a constant.

  1. $T(n) = 2 T (n/2) + cn$
  2. $T(n) = T ( n - 1) + T(1) + cn$
  3. $T(n) = 2T ( n - 1) + cn$
  4. $T(n) = T (n/2) + cn$
asked in Algorithms by Boss (41.1k points)
edited by | 1.9k views

1 Answer

+27 votes
Best answer

Worst case for quick sort happens when $1$ element is on one list and $n-1$ elements on another list.

answered by Veteran (396k points)
edited by

 But according to Cormen, worst case for Quicksort algo occurs when the partitioning produces one subproblem with n-1 elements and another with zero elements ( the nth element is the pivot which gets added to the end of the first subproblem). In fact, it states that even a partition with a 9:1 proportional split also runs in O(n lg n) time. frown

Yes. n-1 elements on one list- 0 on other list is because 'pivot' is ignored- which is anyway placed.

So option B should really be

T(n)=T(n-1)+T(0) +cn

Yes. But can't say the given is wrong either.
Yes sir. Asymptotically they are the same.
Isn't it option D for quick sort?
Option D means we are dividing the elements in half which is not the case for worst condition.
can't say the given is wrong because asymptotically they are the same.Is it?

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
50,132 questions
53,252 answers
70,509 users