Q2: Deriving the Time Complexity of
Insertion Sort
1. Best Case (O(n))
Scenario: The array is already sorted in increasing order.
Reasoning: In this case, the inner `while` loop is never executed because `arr[j] > key` is
always false. So, for each element, there is only one comparison made to check the
condition.
Iterations: The outer loop runs `n - 1` times (from index 1 to `n-1`), and for each iteration,
the inner loop does no work. Thus, the total number of comparisons is `(n - 1)` and no shifts
are made.
Time Complexity: O(n)
2. Worst Case (O(n^2))
Scenario: The array is sorted in reverse order.
Reasoning: In this case, every element has to be compared and shifted to the correct
position in the sorted portion of the array. For each element, the inner `while` loop runs as
many times as its position in the array.
Iterations: For the first element, 1 comparison is made, for the second, 2 comparisons are
made, and so on up to `n-1` comparisons for the last element. This results in `1 + 2 + 3 + ... +
(n-1)` comparisons, which equals `(n(n-1))/2`.
Time Complexity: O(n^2)
3. Average Case (O(n^2))
Scenario: The array elements are in random order.
Reasoning: On average, each element needs to be compared and shifted about halfway
through the already sorted portion of the array. The number of comparisons and shifts is
similar to the worst-case scenario, but about half the inner loop iterations.
Iterations: On average, the inner loop runs `i/2` times for each element `i`, leading to a
similar sum as the worst-case scenario but halved. The total number of comparisons is still
proportional to `(n(n-1))/4`, which simplifies to O(n^2).
Time Complexity: O(n^2)
Summary of Time Complexities
- Best Case: O(n)
- Worst Case: O(n^2)
- Average Case: O(n^2)
