What is the best-case time complexity scenario for Insertion Sort?

The best-case time complexity for Insertion Sort occurs when the input array is already sorted. In this scenario, the algorithm only needs to make a single pass through the array to verify that each element is in the correct position. As Insertion Sort progresses through the elements, it checks each element against its predecessor and finds that no elements need to be moved or swapped.

During this process, the algorithm performs a constant amount of work—specifically, a comparison—for each of the n elements in the array. This results in a linear time complexity of O(n), meaning that the time taken increases directly in proportion to the number of elements.

This contrasts sharply with the average-case and worst-case scenarios for Insertion Sort, which occur when the elements are in reverse order or randomly arranged, leading to a time complexity of O(n^2) due to the nested loops required for shifting elements. The best-case scenario demonstrates the efficiency of Insertion Sort under optimal conditions, highlighting its effectiveness for nearly sorted arrays.