Time Complexity of Insertion Sort Algorithm

Best Case: O(N)

• The best-case time complexity of Insertion Sort occurs when the input array is already sorted.
• In this scenario, each element is compared with its preceding elements until no swaps are needed, resulting in a linear time complexity.
• Therefore, the best-case time complexity is O(N), where n is the number of elements in the array.

Average Case: O(N²)

• The average-case time complexity of Insertion Sort is also O(N²).
• This complexity arises from the nature of the algorithm, which involves pairwise comparisons and swaps to sort the elements.
• Although the exact number of comparisons and swaps may vary depending on the input, the average-case time complexity remains quadratic.

Worst Case: O(N²)

• The worst-case time complexity of Insertion Sort occurs when the input array is in reverse sorted order.
• In this scenario, each element needs to be compared and possibly swapped with every preceding element, resulting in a quadratic time complexity.
• Therefore, the worst-case time complexity is O(N²), where n is the number of elements in the array.