Project ForgeAlgorithms
Complexity Analysis
GATE 2015
Easy
Which one of the following is the recurrence equation for the worst-case time complexity of the Quicksort algorithm for sorting n (≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.
- AT(n) = 2T(n/2) + cn
- T(n) = T(n−1) + T(1) + cn
- CT(n) = 2T(n−1) + cn
- DT(n) = T(n/2) + cn
Explanation
Quicksort's worst case occurs when the chosen pivot is always the smallest or largest element, producing one empty (or size-1) partition and one partition of size n−1 at every level — giving the recurrence T(n) = T(n−1) + T(1) + cn (the cn term is the partitioning cost), which solves to Θ(n²).
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.