0% completed
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 conditionarr[j] > key
is alwaysFalse
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 O(1) for each element.
Mathematically, the total number of comparisons is:
\sum_{i=1}^{n-1} 1 = n - 1
Since the time complexity for each of the n - 1 elements is constant, the best-case time complexity of insertion sort is O(n).
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 n - 1 comparisons for the last element.
The total number of comparisons and shifts in the worst case is:
\sum_{i=1}^{n-1} i = \frac{(n-1) \cdot n}{2}
This sum is approximately O(n^2). Thus, the worst-case time complexity of insertion sort is O(n^2).
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 \frac{i}{2} comparisons, where i is the current position of the element in the loop.
The total number of comparisons is roughly:
\sum_{i=1}^{n-1} \frac{i}{2} = \frac{1}{2} \cdot \frac{(n-1) \cdot n}{2} = \frac{n^2}{4}
Ignoring constant factors, the average-case time complexity is O(n^2).
Summary of Time Complexity for Insertion Sort
Case | Time Complexity |
---|---|
Best Case | O(n) |
Average Case | O(n^2) |
Worst Case | O(n^2) |
In the next lesson, Common Time Complexities, we’ll explore typical time complexities like O(1), O(n), and O(n^2), and how these appear across various algorithms.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible