GATE CSE 2015 | Set 1 | Question: 2

Question

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.

• A. $T(n) = 2 T (n/2) + cn$
• B. $T(n) = T ( n - 1) + T(1) + cn$
• C. $T(n) = 2T ( n - 1) + cn$
• D. $T(n) = T (n/2) + cn$

Comments

recurrence relation for quick sort:-

best case/avg case : T(n) = 2T(n/2) + n

because in best case the elements are divided equally,

worst case : T(n) = T(n-1) + T(1) + cn

worst case arrives when the array is already sorted in either ascending or descending order, thus making n^2 time complexity.

---

@usher 

• Sorted or reverse-sorted input with first/last element as pivot → worst case.

• But even an unsorted array can hit worst case if your pivot choice keeps ending up as min or max.

https://gateoverflow.in/2048/gate-cse-2014-set-3-question-14

---

Can we say T(1) is for the first element? As n >= 2 given in question.

Answer 1

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

Comments

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.}}$

Answer 2

If the pivot is chosen as the last position then there is a left recursive of size (n-1) or right recursive call of size 0.

1.Partition function->O(n)

2.T(n-1) time in left recursive call

3.T(1) time in right recursive call

Recurrence relation: T(n-1)+T(1)+cn

Option B is correct

Answer 3

Quick sort worst case time complexity is n^2, when the array is sorted or almost sorted then Quicksort algorithm runs in O(n^2) time.

The recurrence relation for Quick sort worst case time complexity is

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

Hence, B is Answer.