Which of the following sorting algorithms has the lowest best-case time…
2024
Which of the following sorting algorithms has the lowest best-case time complexity among these standard implementations, assuming bubble sort performs all passes without an early-exit check?
Answer: C. Insertion sort — ConceptBest-case time complexity describes the minimum growth rate of an algorithm’s work over inputs of size n. To compare algorithms fairly, use the stated…
- A.
Selection sort
- B.
Merge sort
- C.
Insertion sort
- D.
Bubble sort
Attempted by 337 students.
Show answer & explanation
Correct answer: C
Concept
Best-case time complexity describes the minimum growth rate of an algorithm’s work over inputs of size n.
To compare algorithms fairly, use the stated implementation assumptions and count the operations that cannot be skipped even on a favorable input.
Application
Selection sort searches the remaining unsorted suffix for its minimum on every pass. Even for sorted input, it performs n(n − 1)/2 comparisons, so its best case is Θ(n2).
Merge sort recursively divides the input and merges subarrays across log n levels. Each level processes n elements, so its best case is Θ(n log n).
Insertion sort grows a sorted prefix. For already sorted input, each new key needs one comparison with no shifts, so the total work grows linearly: Θ(n).
Under the stem’s assumption, bubble sort has no early-exit check and completes all passes. Its comparison count is n(n − 1)/2, so its best case is Θ(n2).
Cross-check and contrast
Using an already sorted array as the favorable input gives the following comparison.
Algorithm | Best case | Reason |
|---|---|---|
Selection sort | Θ(n2) | The minimum search still scans each remaining suffix. |
Merge sort | Θ(n log n) | Every merge level is still processed. |
Insertion sort | Θ(n) | No element shifts are needed. |
Bubble sort without early exit | Θ(n2) | Every scheduled pass is completed. |
Therefore, insertion sort has the lowest best-case time complexity under the stated assumptions.