Insertion Sort Algorithm in DSA Go - Time & Space Complexity

Time Complexity: Insertion Sort Algorithm

O(n²)

Understanding Time Complexity

We want to understand how the time taken by Insertion Sort changes as the list size grows.

How does the number of steps increase when sorting bigger lists?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func insertionSort(arr []int) {
  for i := 1; i < len(arr); i++ {
    key := arr[i]
    j := i - 1
    for j >= 0 && arr[j] > key {
      arr[j+1] = arr[j]
      j--
    }
    arr[j+1] = key
  }
}
    

This code sorts an array by inserting each element into its correct place among the sorted elements to its left.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop that shifts elements to insert the key.
• How many times: The outer loop runs n-1 times, and the inner loop can run up to i times for each i from 1 to n-1.

How Execution Grows With Input

As the list grows, the number of comparisons and shifts grows roughly with the square of the list size.

Input Size (n)	Approx. Operations
10	About 45 comparisons and shifts
100	About 4,950 comparisons and shifts
1000	About 499,500 comparisons and shifts

Pattern observation: Doubling the input size roughly quadruples the work needed.

Final Time Complexity

Time Complexity: O(n²)

This means the time to sort grows roughly with the square of the number of items.

Common Mistake

[X] Wrong: "Insertion Sort always takes the same time no matter the input order."

[OK] Correct: If the list is already mostly sorted, Insertion Sort runs faster because the inner loop does fewer shifts.

Interview Connect

Knowing how Insertion Sort scales helps you understand when to use it and how it compares to faster sorting methods.

Self-Check

"What if we changed the array to be nearly sorted? How would the time complexity change?"