GATE Data Science and Artificial Intelligence 2024 | Sample Paper | Question: 21

Question

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

• A. $\Theta(n\operatorname{logn}), \Theta\left(n^{\wedge} 2\right), \Theta\left(n^{\wedge} 2\right)$
• B. $\Theta\left(n^{\wedge} 2\right), \Theta(n \log n ), \Theta(n \log n)$
• C. $\Theta\left(n^{\wedge} 2\right), \Theta(n\operatorname{logn}), \Theta\left(n^{\wedge} 2\right)$
• D. $\Theta\left(n^{\wedge} 2\right), \Theta\left(n^{\wedge} 2\right), \Theta(n\operatorname{logn})$

   

Answer 1

1. Insertion Sort:

• Worst-case occurs when the array is in reverse order.
• Requires comparing and potentially shifting elements for each insertion.
• Leads to a quadratic time complexity of O(n^2).

2. Merge Sort:

• Consistently divides the array into halves and merges sorted subarrays.
• Worst-case and average-case time complexities are both O(n log n).
• The log n factor comes from the repeated halving of the problem size.

3. Quick Sort:

• Worst-case occurs when the pivot consistently divides the array unevenly.
• Leads to a quadratic time complexity of O(n^2) in this scenario.
• However, the average-case time complexity is O(n log n).

The answer is (C) O(n^2), O(n log n), O(n^2).

Answer 2

Gate PYQ https://gateoverflow.in/39660/gate-cse-2016-set-1-question-13