Best, Worst, and Average Cases

Let’s build on our analysis of insertion sort from the previous lesson. We’ve already covered the general time complexity of insertion sort. In this lesson, we’ll analyze how insertion sort performs in the best, average, and worst cases by calculating time complexity for each scenario.

Insertion Sort: Case Analysis

Insertion sort works by gradually building a sorted section of the list by inserting each new element into its correct position. The time it takes for each insertion depends on where the element needs to be placed, making the input order critical to the algorithm’s performance.

1. Best Case: Already Sorted List

In the best case, the input list is already sorted.

Here’s how insertion sort behaves:

• Inner Loop: The inner while loop checks if the current element is greater than the previous one. Since the list is already sorted, this condition arr[j] > key is always False on the first comparison for each element, and the loop does not run.
• Number of Operations: For each element, the inner loop performs one comparison and then exits, taking constant time for each element.

Mathematically, the total number of comparisons is:

Since the time complexity for each of the elements is constant, the best-case time complexity of insertion sort is .

2. Worst Case: Reverse Sorted List

In the worst case, the input list is sorted in reverse order, meaning every element must be moved to the beginning of the sorted section.

• Inner Loop: For each element, the inner while loop must shift all previous elements to make space. This means for the second element, one comparison and shift occur; for the third, two comparisons and shifts; and so forth.

• Number of Operations: The first element requires 0 comparisons, the second requires 1, the third requires 2, and so on, up to comparisons for the last element.

The total number of comparisons and shifts in the worst case is:

This sum is approximately . Thus, the worst-case time complexity of insertion sort is .

3. Average Case: Randomly Ordered List

In the average case, we assume that the input list is randomly ordered. The number of comparisons for each element depends on where it needs to be inserted within the sorted section. On average, each element is compared with half of the elements in the sorted portion.

• Inner Loop: For each insertion, the inner while loop is expected to run about half as many times as in the worst case.
• Number of Operations: For each element, we perform approximately comparisons, where is the current position of the element in the loop.

The total number of comparisons is roughly:

Ignoring constant factors, the average-case time complexity is .

Summary of Time Complexity for Insertion Sort

In the next lesson, Common Time Complexities, we’ll explore typical time complexities like , , and , and how these appear across various algorithms.