GATE CSE 2016 | Set 1 | Question: 13

Question

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

• A. $\Theta (n \log n)$, $\Theta (n \log n)$ and $\Theta(n^2)$
• B. $\Theta (n^2)$, $\Theta (n^2)$ and $\Theta(n \log n)$
• C. $\Theta (n^2)$, $\Theta (n \log n)$ and $\Theta (n \log n)$
• D. $\Theta (n^2)$, $\Theta (n \log n)$ and $\Theta (n^2)$

Comments

Yes quick sort is not stable

---

This Table should not be referenced blindly, it says Randomized Quick Sort take O(nlogn) but it's not True, Worst Case Time is O(n^2) even in Randomized Quick Sort.

---

THis table is incorrect

BUCKET sort worst case time complexity is $O(n^{2})$

Answer 1

Answer is D.

Insertion sort:  $=  \Theta(n^2)$

Merge sort:      $=  \Theta(n\log n)$

Quick sort:       $=  \Theta (n^2)$

Note : here $\Theta$ is not average case since question asked worst case so $\Theta$ represent worst case only

Answer 2

.Hence the given answer is D

Answer 3

Insertion Sort Worst-Case time complexity=O(n^2)

Merge Sort Worst-Case time complexity=O(nlogn)

Quick Sort Worst-Case time complexity=O(n^2)

Option D is correct

Answer 4

Insertion Sort: O(n²)
-
In the worst case (when the array is in reverse order), each element has to be compared with and shifted past all previously sorted elements. This results in about n² comparisons and shifts.

Merge Sort: O(n log n)
-
Merge Sort in all the case takes O(n log n) time.

Quick Sort: O(n²)
-
In the worst case (such as when the pivot is always the smallest or largest element), the array is divided into very unbalanced parts (1 and n−1 elements). This leads to O(n²) comparisons.

So the answer is option $(D)$.