Chapter 44: DSA Bubble Sort Time Complexity
DSA Bubble Sort Time Complexity – Let’s understand this completely and clearly, like I’m sitting next to you explaining it step-by-step with complete honesty, no shortcuts, and many small examples so you really feel how the time grows.
1. First — What Bubble Sort actually does (quick reminder)
Bubble Sort repeatedly:
- Compares adjacent elements
- If they are in wrong order → swaps them
- After each full pass → the largest remaining element reaches its correct position at the end
Visual example — one pass:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
5 3 8 4 2 ↑ 5>3 → swap → 3 5 8 4 2 ↑ 5<8 → no swap ↑ 8>4 → swap → 3 5 4 8 2 ↑ 8>2 → swap → 3 5 4 2 8 |
After first pass → 8 is at correct position
2. Three different time complexity cases
We always talk about three cases in sorting algorithms:
- Best case
- Average case
- Worst case
Bubble Sort behaves very differently in these cases — especially when we use the optimized version.
Bubble Sort – Two Versions
Naive version (most textbooks show this first):
|
0 1 2 3 4 5 6 7 8 9 |
for i in range(n): for j in range(n-1-i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] |
Optimized version (very important – almost always used in interviews):
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
for i in range(n): swapped = False for j in range(n-1-i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True if not swapped: break # already sorted → no need to continue |
3. Time Complexity – All Three Cases
| Case | When does it happen? | Number of comparisons (approx) | Time Complexity | Explanation |
|---|---|---|---|---|
| Best Case | Array is already sorted | ~ n comparisons | O(n) | Optimized version stops after one pass (no swaps) |
| Average Case | Random order | ~ n² / 2 comparisons | O(n²) | Still does almost full work |
| Worst Case | Array is reverse sorted | ~ n² / 2 comparisons | O(n²) | Does maximum swaps and maximum passes |
4. Detailed Breakdown – How many comparisons really happen?
Let’s count exactly (very important for understanding)
Array size n = 5
Naive version — always does full work:
Pass 1: 4 comparisons Pass 2: 3 comparisons Pass 3: 2 comparisons Pass 4: 1 comparison
Total comparisons = 4 + 3 + 2 + 1 = 10 General formula: n(n-1)/2 = O(n²)
Optimized version — best case (already sorted):
Pass 1: n-1 comparisons, 0 swaps → swapped = False → break
Total comparisons = n-1 ≈ O(n)
Worst case (reverse sorted) — even optimized version does full work:
Every pass has many swaps → swapped = True every time → no early break Total comparisons still n(n-1)/2 = O(n²)
5. Very Clear Comparison Table
| n | Best Case (optimized) | Average / Worst Case | Number of passes (worst) | Approx comparisons (worst) |
|---|---|---|---|---|
| 10 | ~10 | O(100) | 10 | 45 |
| 100 | ~100 | O(10,000) | 100 | 4,950 |
| 1,000 | ~1,000 | O(1 million) | 1,000 | ~500,000 |
| 10,000 | ~10,000 | O(100 million) | 10,000 | ~50 million |
| 100,000 | ~100,000 | O(10 billion) | 100,000 | ~5 billion |
Real feeling:
- n = 10,000 → worst case ~50 million operations → acceptable (~0.05–0.5 sec)
- n = 100,000 → ~5 billion operations → usually too slow (5–50 seconds or more)
6. Summary – Bubble Sort Time Complexity (what you should say in interviews)
| Version | Best Case | Average Case | Worst Case | Important note |
|---|---|---|---|---|
| Naive Bubble Sort | O(n²) | O(n²) | O(n²) | No early stopping |
| Optimized Bubble Sort | O(n) | O(n²) | O(n²) | Stops early if already sorted |
Most common interview answer:
“Bubble Sort has O(n²) time complexity in both average and worst cases because it performs approximately n(n-1)/2 comparisons. In the best case (already sorted array), the optimized version can terminate after just one pass with O(n) comparisons by using a swapped flag. Due to quadratic time complexity, Bubble Sort is not efficient for large inputs (n > 10,000) and is mainly used for educational purposes or very small arrays.”
7. Quick Cheat Sheet – Bubble Sort
| Question | Answer |
|---|---|
| Worst-case time complexity | O(n²) |
| Best-case time complexity (optimized) | O(n) |
| Average-case time complexity | O(n²) |
| Space complexity | O(1) (in-place) |
| Stable? | Yes |
| Adaptive? | Yes (with optimization) |
| When to use | Learning, very small n (< 50–100), interviews when asked to code simple sort |
Do you want me to continue with any specific part?
Very common follow-up questions people ask after this:
- Why is Bubble Sort O(n²) even after optimization?
- Bubble Sort vs Insertion Sort – which is better in practice?
- How many swaps does Bubble Sort perform in different cases?
- Can we make Bubble Sort faster? (Cocktail sort / Comb sort)
- Prove mathematically why best case is O(n) in optimized version
Just tell me which one you want next — I’ll explain it in the same detailed, friendly, teacher style with clear examples 😊
