The GATE Grind

GATE 2014 CS (CS3) – Question 24

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

Quicksort on n array elements always chooses the central array element as pivot. Find the tightest upper bound on worst-case performance.

  1. $O(n^2)$
  2. $O(n\log n)$
  3. $\Theta(n\log n)$
  4. $O(n^3)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $O(n^2)$

Explanation

The central array position need not hold a median value. Adversarial values can make each selected pivot an extreme, leaving subproblems of sizes n−1,n−2,… . Summing partition work gives **O(n²),A** as the tight worst-case bound. A middle index does not guarantee balanced partitions.