GATE CS 2016 Set 1 Q.23 (CS Q.13): Searching and Sorting Algorithms

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

$\Theta(n \log n)$ , $\Theta(n \log n)$ , and $\Theta(n^2)$

$\Theta(n^2)$ , $\Theta(n^2)$ , and $\Theta(n \log n)$

$\Theta(n^2)$ , $\Theta(n \log n)$ , and $\Theta(n \log n)$

$\Theta(n^2)$ , $\Theta(n \log n)$ , and $\Theta(n^2)$

Official answer and solution

Solution

Recall the asymptotic worst-case time complexities of fundamental comparison-based sorting algorithms.

Examine the worst-case time complexity of each algorithm:

Insertion Sort: In the worst case (reverse sorted input), each element $i$ is compared with and shifts all $i-1$ preceding elements. Total comparisons $= \sum_{i=1}^{n-1} i = \Theta(n^2)$ .
Merge Sort: Divides the list into two halves ( $2 T(n/2)$ ) and merges them in $\Theta(n)$ time. By the Master Theorem, $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$ in all cases (worst, average, and best).
Quick Sort: In the worst case (e.g. partition produces highly unbalanced subproblems of sizes $0$ and $n-1$ ), the recurrence is $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$ .

Therefore, the worst-case running times are $\Theta(n^2)$ , $\Theta(n \log n)$ , and $\Theta(n^2)$ , respectively.

Final answer

Common trap

Stating $\Theta(n \log n)$ for Quicksort, which is its average-case running time, rather than its worst-case running time $\Theta(n^2)$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.