Formula & Calculator
Bubble Sort Worst-Case Time Complexity
Gives the exact number of comparisons bubble sort performs in the worst case, illustrating its O(n²) time complexity.
Interpretation
Bubble sort worst‑case comparisons: for n elements, it performs n(n−1)/2 comparisons. This occurs when the array is in reverse order. Example: n=10 → comparisons = 10×9/2 = 45.
Variables
| Symbol | Quantity | Unit |
|---|---|---|
| T(n) | Number of comparisons | |
| n | Number of elements |
What it means
Bubble sort is a simple comparison‑based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The worst‑case scenario for bubble sort is when the input is in reverse order, requiring the maximum number of comparisons and swaps. For n elements, the number of comparisons is n‑1 for the first pass, n‑2 for the second, ..., down to 1, totaling n(n‑1)/2. This is O(n²) time complexity. Although bubble sort is easy to understand and implement, it is inefficient for large datasets and is rarely used in practice except for educational purposes. Its space complexity is O(1) (in‑place). The algorithm can be optimized with early termination if no swaps occur, making it O(n) on nearly sorted data. However, its worst‑case performance makes it unsuitable for production environments where performance matters. The formula is often used as a classic example of quadratic time complexity in algorithm analysis.
Worked example
Bubble Sort Worst‑Case – Two Examples
Real‑World| Parameter | Value |
|---|---|
| n | 10 |
| Comparisons | 10×9/2 = 45 |
| Parameter | Value |
|---|---|
| n | 1000 |
| Comparisons | 1000×999/2 = 499,500 |
Common mistakes
- Worst‑case only: This formula gives the number of comparisons in the worst case (reverse‑sorted input). In the best case (already sorted), it makes only n−1 comparisons.
- Swaps vs. comparisons: The count n(n−1)/2 is for comparisons; the number of swaps can be less.
- Optimisation: Bubble sort can be optimised by stopping early if no swaps occur; the worst‑case still holds.
- Time complexity: O(n²) in worst case, but the exact number is n(n−1)/2.
- For loop bounds: When implementing, use nested loops with decreasing inner range; otherwise you may overcount.
Applications
Bubble sort is one of the simplest sorting algorithms, with a worst‑case time complexity of n(n−1)/2 comparisons (O(n²)). Although inefficient for large datasets, it is often used for educational purposes to illustrate sorting concepts and algorithm analysis. Its applications are limited to small datasets or nearly‑sorted arrays, where it can be optimised with early termination. In practice, bubble sort may appear in embedded systems with very limited resources, or in code that requires minimal implementation effort. Its simplicity also makes it a candidate for demonstrating algorithmic improvements like cocktail shaker sort. Understanding bubble sort is valuable for learning about time complexity, loops, and the importance of choosing the right algorithm for the task.
- Educational teaching of sorting algorithms
- Sorting very small datasets (≤ 50 elements)
- Embedded systems with constrained memory
- Demonstration of optimisation techniques (early exit)
- Comparative analysis of sorting algorithms
Frequently Asked Questions
In the worst case (array sorted in reverse order), bubble sort makes n*(n‑1)/2 comparisons. This is because the outer loop runs n‑1 times, and the inner loop runs n‑i‑1 times. Summing gives n(n‑1)/2. This is O(n²).
If the array is already sorted, the standard bubble sort still makes n(n‑1)/2 comparisons if no optimization is added. However, by adding a swap flag to break early when no swaps occur, the best‑case becomes O(n) (one pass with zero swaps). This optimized version is often used for nearly‑sorted data.
- Assuming it is always O(n²) – with early termination, it can be O(n) on sorted data.
- Counting swaps incorrectly – comparisons are n(n‑1)/2, but swaps can be fewer.
- Using the formula for the number of passes – the outer loop runs n‑1 times at most.
- Ignoring the constant factor – though O(n²), the constant is small, making it useful for tiny arrays.
- Bubble sort – stable, but has many swaps; best case O(n) with flag.
- Selection sort – not stable, always O(n²) comparisons, but fewer swaps.
- Insertion sort – stable, best case O(n) for sorted data, and often faster than bubble sort in practice due to fewer moves.
Bubble sort is an in‑place algorithm, requiring only O(1) extra space (a few variables for swapping and the flag). It does not use any auxiliary arrays.
Bubble sort is only suitable for very small datasets (e.g., n < 20) where its simplicity and lack of overhead outweigh the O(n²) time. It is also used in embedded systems with severe memory constraints where O(1) space is critical.
With the optimized version, bubble sort becomes O(n) for already‑sorted data. For nearly‑sorted data (e.g., only a few elements out of place), it will finish after a few passes, making it efficient. This is why it is sometimes used as a final pass in hybrid algorithms like Timsort.
Cocktail shaker sort (bidirectional bubble sort) passes through the array in both directions alternately. It can reduce the number of passes in some cases, but the worst‑case complexity remains O(n²). It is also a stable, in‑place algorithm.
In the worst case, the inner loop compares adjacent elements each time. For pass i (0‑based), the inner loop runs (n‑i‑1) times. Summing over i = 0 to n‑2 gives Σ(n‑i‑1) = (n‑1) + (n‑2) + ... + 1 = n(n‑1)/2. This is the total number of comparisons.
You should know its O(n²) worst‑case, O(n) best‑case with optimization, O(1) space, and stability. Be able to implement it and explain when it might be used (small or nearly‑sorted arrays). Also, understand how the swap flag improves performance.