The GATE Grind

GATE 2015 CS – Question 14

Algorithms · Searching, Sorting and Hashing · 1 mark · Multiple choice

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

  1. $T(n) = 2T(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$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $T(n) = T(n-1) + T(1) + cn$

Explanation

In the worst case the pivot is the smallest or largest element, so partitioning costs $cn$ and leaves one subproblem of size $n-1$ and one of size 1. That gives $T(n) = T(n-1) + T(1) + cn$.