edited by
11,398 views
33 votes
33 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$
edited by

3 Answers

Best answer
42 votes
42 votes

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

edited by
0 votes
0 votes
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.
0 votes
0 votes
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:

Related questions

31 votes
31 votes
2 answers
2
6 votes
6 votes
3 answers
3
65 votes
65 votes
12 answers
4