Complexity Analysis

Let’s analyze how bubble sort performs with different input sizes.

Time Complexity

Worst Case: O(n²)

• Array is in reverse order
• Every comparison results in a swap
• Total comparisons: n(n-1)/2

Best Case: O(n)

• Array is already sorted (with optimization)
• Only one pass needed
• Without optimization: still O(n²)

Average Case: O(n²)

• Random order
• About half the comparisons result in swaps

Visualizing Complexity

Space Complexity

O(1) - Constant Space

• Only uses a few variables
• Sorts in-place (modifies original array)
• No additional arrays needed

Comparison with Other Algorithms

Algorithm	Best	Average	Worst	Space
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)

Bubble sort is slower but simpler than most alternatives.

When Input Size Doubles

• n = 10: ~45 comparisons
• n = 20: ~190 comparisons (4x more)
• n = 40: ~780 comparisons (16x more)

The number of operations grows quadratically, not linearly.

Real-World Impact

For 1,000 elements:

• Bubble sort: ~500,000 operations
• Quick sort: ~10,000 operations (50x faster)

This is why bubble sort isn’t used in production.

What’s Next?

Let’s see how we can optimize bubble sort to perform better in some cases.