Bubble Sort Algorithm in DSA Go - 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 many steps does Bubble Sort need to sort a list of numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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: 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.

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 work, showing a square growth pattern.

Final Time Complexity

Time Complexity: O(n²)

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

Common Mistake

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

[OK] Correct: If the list is already sorted, Bubble Sort can finish faster because it does fewer swaps and can stop early if optimized.

Interview Connect

Understanding Bubble Sort's time complexity helps you compare it with faster sorting methods and shows your grasp of algorithm efficiency.

Self-Check

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