Bubble Sort Algorithm in DSA C++ - 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 comparisons and swaps increase when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}
    

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

Identify Repeating Operations

• Primary operation: Comparing and possibly swapping adjacent elements inside the inner loop.
• How many times: The inner loop runs about n times for each of the n passes of the outer loop, so roughly n x n = n² times.

How Execution Grows With Input

As the list size grows, the number of comparisons grows much faster because each element is compared with many others multiple times.

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

Pattern observation: When the input size doubles, the operations roughly quadruple, showing a square growth pattern.

Final Time Complexity

Time Complexity: O(n²)

This means the time taken grows roughly with the square of the number of elements, so sorting gets much slower as the list grows.

Common Mistake

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

[OK] Correct: Each element is compared many times in nested loops, so the total comparisons 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 and shows your grasp of algorithm basics.

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?"