Bubble Sort Algorithm in DSA Javascript - Time & Space Complexity

Time Complexity: Bubble Sort Algorithm

O(n²)

Understanding Time Complexity

We want to understand how the time taken by Bubble 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.

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}
    

This code sorts an array by repeatedly swapping adjacent elements if they are in the wrong order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing and possibly swapping adjacent elements inside nested loops.
• How many times: Outer loop runs (n-1) times; inner loop runs decreasing times from (n-1) down to 1.

How Execution Grows With Input

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

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

Pattern observation: Doubling the input size roughly quadruples the number of operations.

Final Time Complexity

Time Complexity: O(n²)

This means the time to sort grows quickly as the list gets bigger, roughly proportional to the square of the list size.

Common Mistake

[X] Wrong: "Bubble Sort only takes time proportional to the list size (O(n)) because it just compares neighbors."

[OK] Correct: Because it uses nested loops, it compares many pairs multiple times, making the total steps grow much faster than the list size.

Interview Connect

Understanding Bubble Sort's time complexity helps you appreciate why more efficient sorting methods are used in real projects.

It also shows your ability to analyze how algorithms behave as data grows, a key skill in coding interviews.

Self-Check

"What if we add a flag to stop early if no swaps happen in a pass? How would the time complexity change in the best case?"