Big-O growth: what each complexity class actually costs
Your data
Two algorithms head to head
The constant is everything the notation throws away: allocations, cache misses, the work inside each step. Give one algorithm a heavier constant and watch where it stops mattering.
This page does not read your loop. Guessing a complexity from source code would be a guess wearing the clothes of a measurement: a loop can break early, a single call inside it can hide the real cost, and recursion rarely reads as what it does. You choose the class; what the page computes from there is exact.
Results
| Where one overtakes the other, in items | — |
| Operations of each, at the size above | — |
With the numbers this page starts with, the crossover sits at 439 items. An engineer who reaches for the better class on a list of two hundred has made the program slower and the code harder, and the notation gave no warning, because the notation is about what happens eventually and not about what happens to you.
Every class at this size
| Class | Operations | Time | Multiplied by, if the input doubles |
|---|
The last column is the one worth staring at, because it is the column nobody carries in their head. Linear work doubles. Quadratic work quadruples. Exponential work gets squared: with a thousand items already in play, doubling the input multiplies the cost by two to the thousandth power, a number with three hundred and two digits.
Factorial is worse in a way that has nothing to do with doubling. Adding a single item multiplies the cost by the new count, so the twenty-first item costs twenty-one times the whole twenty-item problem. That is why an exact travelling salesman over twenty cities is 2.4 million million million steps, or seventy-seven years at a billion a second, while the same twenty cities under two to the n finish in a thousandth of one.
It also explains why the gap between classes is boring at small sizes and brutal at large ones. At ten items, n log n and n squared are three times apart, which no user would notice. At a thousand items they are a hundred times apart, and at a million they are fifty thousand times apart. The same two algorithms, the same code, nothing changed but the input.
So the honest reading of a complexity class is a promise about the shape of the curve, not about speed. It tells you how the cost reacts when the input grows, and says nothing at all about whether it is fast today, on your machine, at the size you actually have.
Does a better complexity class mean a faster program?
Not at your size, necessarily. The class describes how the cost reacts as the input grows; it says nothing about the work inside each step, and that work is exactly what the notation throws away.
With the numbers this page starts with, the quadratic algorithm with a light constant beats the n log n one with a constant of fifty for every input below 439 items. Above that the better class pulls ahead and never gives the lead back.
Why does this page not read my code?
Because guessing a complexity from source is a guess wearing the clothes of a measurement. A loop can break early, one call inside it can hide the real cost, and recursion rarely reads as what it does.
So the class is your input here, not the page's opinion. Everything computed from it is exact arithmetic, and nothing on the page pretends to know what your loop does.
What actually happens when the input doubles?
Linear work doubles and quadratic work quadruples, which most people carry in their head. Exponential work gets squared, which almost nobody does: at a thousand items, doubling the input multiplies the cost by two to the thousandth power.
Factorial does not even work that way. Adding one single item multiplies the cost by the new count, so the twenty-first item costs twenty-one times the entire twenty-item problem.
| Class | Multiplied by when the input doubles, at a thousand items |
|---|---|
| O(n) | 2 |
| O(n log n) | 2,2 |
| O(n²) | 4 |
| O(n³) | 8 |
| O(2ⁿ) | 1,07 x 10^301 |
Why is an exact travelling salesman impossible at twenty cities?
Because twenty factorial is 2.4 million million million steps, which at a billion operations a second is seventy-seven years. The same twenty items under two to the n take about a thousandth of a second.
That is the practical difference between exponential and factorial, and it is why the two are worth separating instead of both being filed under impossible.
Reactions
0
0 Comments
Be the first to comment