Complexity Comparison Generator
Big-O deliberately ignores constant factors, and this shows exactly what that costs. An n log n algorithm with a twenty-times overhead loses to a plain n-squared one until the input gets big enough — and "big enough" is a number you can compute rather than a hand-wave. Sometimes the crossover is at n = 8; sometimes it is past any size you will ever meet, and then the asymptotically worse algorithm is simply the right choice. That pairing is the default because it is the classic one, but either side can be any of six growth functions, from a constant up to 2^n.
What this generator does
Tabulates operation counts for two algorithms across doubling input sizes — one carrying a constant overhead, the other none — and identifies the size at which the first overtakes the second. Either growth function is yours to pick from constant, log n, n, n log n, n squared and 2^n, which is fifteen pairings.
How to use this tool
- Pick the two growth functions to compare — the better-growing one on the left.
- Set how much overhead the better-growing algorithm carries.
- Read down the table and find where the winner changes.
- Push the overhead up and watch the crossover move right.
- Notice when it disappears from the range entirely.
Understanding the controls
- Better growth, with the overhead
- The algorithm that eventually wins: constant, log n, n, n log n, n squared or 2^n. It is the one paying the overhead, because that is the comparison worth making.
- Worse growth, no overhead
- The algorithm with no overhead, chosen from the same six. It has to grow faster than the first, or there is nothing to cross over.
- Constant overhead
- How many times more work each step of the better-growing algorithm costs. Between 2 and 200 — at the high end the crossover leaves the table entirely.
Common use cases
- Deciding whether an asymptotically better algorithm is worth it
- Showing why constant factors matter at real input sizes
- Teaching what big-O does and does not promise
- Justifying a simple algorithm for small inputs
- Comparing growth rates without writing benchmarks
How this generator works
Each cell is the constant times the growth function at that size, so the table is arithmetic rather than measurement. The check recomputes every cell from the growth function it claims, requires the counts to be non-decreasing, and confirms the stated crossover is the first size where the order changes.
Randomness and fairness
Nothing here is random. The same overhead always produces the same table, which is why there is no seed.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- The six growth functions on offer are the standard teaching set; a pairing outside them is not available.
- Operation counts are abstract — real performance depends on cache behaviour, memory and constant factors this cannot see.
- Sizes stop at 1,024, so a very large overhead has no crossover in range.
- Nothing is measured; this is arithmetic on growth functions, not a benchmark.
- Tables are not stored between visits.
Privacy and your data
The table is computed in your browser from the number you enter. Neither is transmitted or stored; what is measured is that the tool was used.
Related generators
- Binary Search Scenario GeneratorSorted lists with the full binary search trace, every step's range shown, and the logarithmic bound as the check.
- Sorting Algorithm Trace GeneratorAn array, an algorithm, and the state after every pass, with the comparison and move counts that distinguish the three.
- Topological Sort Challenge GeneratorDependency sets with a valid order and a count of how many valid orders exist in total.
- Hash Table Scenario GeneratorKeys distributed into buckets by modulo hashing, with collisions, chain lengths and empty buckets all recounted from the table.