Insertion Sort Algorithm in DSA Javascript - Time & Space Complexity

Time Complexity: Insertion Sort Algorithm

O(n²)

Understanding Time Complexity

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

Specifically, how many steps does it take to sort more numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner while loop that shifts elements to insert the key in the right place.
• How many times: The outer for loop runs once for each element (n-1 times), and the inner while loop can run up to i times for each outer loop step.

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: When input size doubles, operations roughly quadruple, showing a squared growth.

Final Time Complexity

Time Complexity: O(n²)

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

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 much faster, closer to linear time, because fewer shifts are needed.

Interview Connect

Knowing how Insertion Sort behaves helps you understand sorting basics and compare it with faster methods, which is a useful skill in interviews and real coding.

Self-Check

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