The Gateway to Computer Science Excellence
+25 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$
in Algorithms by Boss (30.7k points)
edited by | 2.2k views
What does cn indicates ?
It means any constant which is multiplied to $\mathbf n$.

1 Answer

+30 votes
Best answer

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

by Veteran (430k 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?
For Worst Case correct Recurrences are:

$\mathbf{T(n) = T(0) + T(n-1) + \theta (n)}$

which is the same as:

$\mathbf{T(n) = T(n-1) + \theta (n)}$

The solution of this recurrence is $\mathbf{\theta (n)}$

Maybe the examiner have something to do with $\mathbf{n \ge 2}$ case. If this isn't the case, then the options are definitely wrong $\color{blue} {\text{According to Cormen and Wikipedia.}}$

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,741 questions
57,252 answers
104,697 users