What is the best-case time complexity of insertion sort, and when does it occur?
Correct answer C. O(n), when the input is already sorted
Explanation
Insertion sort compares each new element with the one before it; in a sorted array no element needs to move, so each step costs one comparison and the total is linear. Reverse-sorted input is the worst case, O(n²), since every element shifts all the way left. This adaptivity makes insertion sort a good choice for small or nearly sorted data.
Answer checked How we write and check questions
Discussion