What is the running time of an insertion sort algorithm if the input is…
2024
What is the running time of an insertion sort algorithm if the input is pre-sorted?
- A.
O(N^2)
- B.
O(N log N)
- C.
O(N)
- D.
O(M log N)
Attempted by 324 students.
Show answer & explanation
Correct answer: C
When the input is pre-sorted, insertion sort performs optimally because each element is already in the correct position relative to the previous elements.
The inner loop checks whether the current element needs to be moved left. In a pre-sorted array, this condition fails immediately for every element.
As a result, only one comparison is made per element, and no swaps are needed.
This leads to a linear running time of O(N), which is the best-case time complexity for insertion sort.