The GATE Grind

GATE 2016 CS – Question 23

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

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\Theta(n^2)$, $\Theta(n \log n)$, and $\Theta(n^2)$

Explanation

Insertion sort takes $\Theta(n^2)$ on a reverse-sorted input. Merge sort always takes $\Theta(n \log n)$. Quick sort takes $\Theta(n^2)$ when the pivot is always the smallest or largest element.