The Gateway to Computer Science Excellence
+25 votes
2.2k views

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
0
What does cn indicates ?
0
It means any constant which is multiplied to $\mathbf n$.

1 Answer

+30 votes
Best answer

B.
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
+6

 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

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

So option B should really be

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

+3
Yes. But can't say the given is wrong either.
+5
Yes sir. Asymptotically they are the same.
0
Isn't it option D for quick sort?
0
Option D means we are dividing the elements in half which is not the case for worst condition.
0
can't say the given is wrong because asymptotically they are the same.Is it?
0
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.}}$
Answer:

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
198,061 comments
104,697 users