Bubble Sort Complexity Calculator
Solve the worst-case comparison count for bubble sort, going either from array size to comparisons or back — with step-by-step math, a growth-curve chart, and an operations-to-time estimator.
n ↑ — quadratic growth
Doubling n roughly quadruples T(n) — the defining signature of an O(n²) algorithm. This is why bubble sort is fine for small n but becomes impractical fast as n grows.
Best case vs. worst case
An optimized bubble sort that exits early once no swaps occur needs only n−1 comparisons on an already-sorted array (O(n)) — dramatically better than the O(n²) worst case.
Why it doesn't scale
Algorithms with O(n log n) worst-case behavior, like merge sort or heapsort, pull far ahead of bubble sort as n grows — see the growth chart and reference table below.
Comparisons vs. swaps
In the worst case every comparison also triggers a swap, so comparisons and swaps are equal. In the best case, comparisons stay at O(n) while swaps drop all the way to zero.
How to Use This Calculator
The bubble sort worst-case relation links two quantities: array size n, and the number of comparisons T(n). Pick which one you want the tool to solve, then fill in the other.
1. Choose what to solve for
Pick T(n) (comparisons from array size) or n (array size from a comparison count) — the tool rearranges the formula automatically.
2. Pick a quick array size, or type your own
Use a preset (10 / 100 / 1,000 / 10,000 / 100,000) or enter any custom array size for n.
3. Read the result and steps
The result card shows the solved value plus engineering (×10ⁿ) notation. The step-by-step panel shows exactly how the number was reached.
4. Check the growth chart
The chart plots bubble sort's O(n²) curve against O(n log n) and O(n) for the same range, so you can see where the gap opens up.
5. Switch to Advanced for more depth
Advanced mode adds sensitivity to a 1% change in the known input, plus best-case, average-case, and swap-count companion metrics.
6. Estimate real time, or copy the result
Use the operations-to-time converter further down the page to turn a comparison count into a real time estimate, or "Copy result" to grab the solved value.
What This Tool Offers
Built around bubble sort's worst-case comparison formula T(n) = n(n−1)/2, one of the first complexity results taught in any algorithms course.
Solve either direction
Go from array size to worst-case comparisons, or work backwards from a comparison count to the array size that produced it.
Quick size presets
One-click presets for 10, 100, 1,000, 10,000, and 100,000 elements — the same sizes used in the reference tables below.
Live growth-curve chart
See bubble sort's O(n²) curve plotted against O(n log n) and O(n) for the same input sizes, updating with your current n.
Companion complexity metrics
Advanced mode reports best-case and average-case comparison counts alongside the worst case, plus the equivalent swap count.
Built-in sensitivity check
See exactly how much a 1% change in array size moves the comparison count — a concrete feel for what "quadratic" means.
Operations-to-time estimator
Turn any comparison count into a real wall-clock time estimate at a chosen processor speed, further down the page.
Reference Tables & Conversions
An operations-to-time estimator, plus lookup tables comparing bubble sort against other common sorting algorithms and complexity classes.
Operations → time estimator
Complexity Growth Reference
How different Big-O growth rates compare at the same input size — this is why the choice of algorithm matters more as n grows.
| Growth rate | n = 10 | n = 100 | n = 1,000 |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | ≈3.3 | ≈6.6 | ≈10.0 |
| O(n) | 10 | 100 | 1,000 |
| O(n log n) | ≈33 | ≈664 | ≈9,966 |
| O(n²) — bubble sort | 100 | 10,000 | 1,000,000 |
| O(2ⁿ) | 1,024 | ≈1.27 × 10³⁰ | astronomically large (300+ digits) |
Sorting Algorithm Complexity Comparison
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting sort | O(n+k) | O(n+k) | O(n+k) | O(n+k) | Yes |
Bubble Sort Worst-Case Comparisons by Array Size
| n | T(n) comparisons | Approx. time @ 1 GHz |
|---|---|---|
| 10 | 45 | 45 ns |
| 100 | 4,950 | 4.95 µs |
| 1,000 | 499,500 | ≈0.5 ms |
| 10,000 | 49,995,000 | ≈50 ms |
| 100,000 | 4,999,950,000 | ≈5 s |
| 1,000,000 | 499,999,500,000 | ≈8.3 minutes |
What Does T(n) = n(n−1)/2 Measure?
Bubble sort repeatedly steps through an array, comparing each pair of adjacent elements and swapping them if they're out of order. In the worst case — an array sorted in exactly reverse order — every one of the n(n−1)/2 possible pairs gets compared. That count, T(n), is the classic textbook example of quadratic, O(n²), time complexity.
Bubble Sort Complexity Formula
The defining relationship is:
This is exactly the sum of the first (n−1) positive integers, which is also why it's sometimes written as the "triangular number" of (n−1). Rearranged to solve for n given a comparison count:
Bubble Sort Complexity Variables
| Symbol | Meaning | Notes |
|---|---|---|
| n | Number of elements in the array | Should be a non-negative integer in practice |
| T(n) | Worst-case number of comparisons | Also equals the worst-case number of swaps |
How Array Size Affects Comparisons
Because T(n) is quadratic in n, comparisons grow much faster than the array itself: doubling n roughly quadruples T(n), and a tenfold increase in n produces roughly a hundredfold increase in comparisons. This quadratic blow-up is exactly why bubble sort is taught as a cautionary example — it's simple to understand and implement, but impractical for anything beyond small or already-nearly-sorted inputs.
Bubble Sort Complexity Calculation Examples
T(10) = 10 × (10 − 1) / 2 = 10 × 9 / 2
T(10) = 45 comparisons
n = ( 1 + √(1 + 8×4,950) ) / 2 = ( 1 + √39,601 ) / 2 = ( 1 + 199 ) / 2
n = 100 elements
Frequently Asked Questions
It's the total number of adjacent-element comparisons a naive bubble sort makes in the worst case, when every pass has to run its full length because the array starts in reverse order. It's also the sum of the integers from 1 to (n−1).
In the worst case, yes — every comparison finds an out-of-order pair, so every comparison triggers a swap. In the average or best case, many comparisons find pairs already in order, so swaps drop below the comparison count (down to zero in the best case).
A common optimization tracks whether any swaps happened during a pass and stops early if none did. On an already-sorted array, that optimized version only needs a single O(n) pass — but this best case doesn't change the O(n²) worst-case or average-case behavior the formula on this page describes.
Badly — see the growth chart and the algorithm comparison table above. Once n reaches even a few thousand, O(n log n) algorithms like merge sort or quicksort finish enormously faster than bubble sort's O(n²) worst case.
The T(n) formula on this page specifically describes the worst case. An optimized bubble sort on an already-sorted array needs only n−1 comparisons and zero swaps — see the best-case figure in the companion metrics in Advanced mode.
Worst-case analysis gives a guaranteed upper bound on how long an algorithm can possibly take, regardless of input — which matters for reliability and for comparing algorithms on equal footing, even though real-world inputs are often kinder than the worst case.
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
Related calculators · Algorithms
Recently updated formulas
Suggest an improvement
Found a mistake? Have a better example? Let us know.
You may send up to 3 suggestions per 24 hours.