Bubble Sort vs Quicksort: Cost by Input Size

By Victor Arce

Big-O tells you the shape of an algorithm's growth, but the shape is abstract until you watch two real algorithms pull apart. Here we put bubble sort and quicksort on the same axes and count the one thing they both do: compare two values. Bubble sort is O(n²)O(n²) — quadratic time: the work grows with the square of the number of items.; quicksort is O(n log n)O(n log n) — linearithmic time: n times log n; the best worst-case for comparison sorts. on average. The question this article answers by feel, not just by formula, is: how much does that difference actually matter?

Slide the input size n and watch. The vertical marker carries a dot on each curve, and the readout shows the live comparison counts and how many times more work bubble sort is doing.

What the two curves count

Both numbers are comparisons — the basic operation a sort spends its time on.

• Bubble sort — n(n−1)/2. It walks the list over and over, comparing each neighbouring pair, so the count is essentially every pair of elements. That's the classic O(n²)O(n²) — quadratic time: the work grows with the square of the number of items. shape: double n and the work roughly quadruples.
• Quicksort — about 1.39·n·log₂n. Each partition splits the data and recurses on the pieces, so the total comparisons grow only a little faster than linearly. On the same axes it barely lifts off the floor.

The constants (the 1.39, the ½) are real, but Big-O deliberately ignores them — and the plot shows why that's the right call. No constant can rescue the O(n²)O(n²) — quadratic time: the work grows with the square of the number of items. curve once n is large enough.

Small n is the honest caveat

Drag n down toward the left edge. For a handful of items the two counts are close, and bubble sort's tiny code and zero overhead can even win outright. This is not a footnote — real libraries (Timsort, introsort) switch to insertion sort for small subarrays for exactly this reason. The lesson isn't "quadratic is always bad"; it's "quadratic doesn't scale."

Why the gap is the whole story

Now drag n to the right. At n = 100 bubble sort already does roughly 5× the comparisons; push it further and the ratio keeps climbing without bound. A faster CPU multiplies your speed by a constant, but moving from O(n²)O(n²) — quadratic time: the work grows with the square of the number of items. to O(n log n)O(n log n) — linearithmic time: n times log n; the best worst-case for comparison sorts. changes the curve itself — and at scale the curve always wins. That is the entire reason we study complexity classes before we tune code.

Back to Sorting Algorithms