Which of the following sorting algorithms has the minimum running time…
2013
Which of the following sorting algorithms has the minimum running time complexity in the best and average case?
- A.
Insertion sort, Quick sort
- B.
Quick sort, Quick sort
- C.
Quick sort, Insertion sort
- D.
Insertion sort, Insertion sort
Attempted by 224 students.
Show answer & explanation
Correct answer: A
To determine the correct option, we analyze the time complexities of common sorting algorithms in their best and average cases.
In the best case, Insertion Sort runs in O(n) time when the input array is already sorted. This is the minimum possible complexity for comparison-based sorting in the best case.
In the average case, Quick Sort runs in O(n log n) time. This is generally faster than Insertion Sort's average case of O(n^2).
Therefore, the pair corresponding to minimum best-case and average-case complexities is Insertion Sort and Quick Sort respectively.