Big-O Complexity Calculator
Put a wall-clock number on a complexity class. Enter your input size and see which algorithms finish instantly, which finish overnight, and which never finish at all.
Your problem
Input size and how fast one operation actually runs on your machine.
Logarithmic, from 10 to a billion.
Big-O drops constant factors, so this is the knob that puts them back.
Slowest algorithm that still finishes in a second at n = 10K
O(n²)
Nested loop, bubble sort, naive pair comparison. Everything above it on the table takes longer than a second.
Runtime at n = 10,000
Assuming 1B operations per second.
| Complexity | Operations | Estimated time | If n doubles | Typical example |
|---|---|---|---|---|
| O(1) | 1 | 1 ns | 1.00× work | Hash map lookup, array index |
| O(log n) | 13 | 13 ns | 1.08× work | Binary search, balanced tree lookup |
| O(√n) | 100 | 100 ns | 1.41× work | Trial-division primality test |
| O(n) | 10,000 | 10.0 µs | 2.00× work | Single pass over a list |
| O(n log n) | 132,877 | 132.9 µs | 2.15× work | Quicksort, mergesort, heapsort |
| O(n²) | 100,000,000 | 100.0 ms | 4.00× work | Nested loop, bubble sort, naive pair comparison |
| O(n³) | 1,000,000,000,000 | 16.7 min | 8.00× work | Naive matrix multiplication, Floyd-Warshall |
| O(2ⁿ) | 10^3010 | 10^2994 years | 10^3010× work | Naive recursive subsets, unmemoised Fibonacci |
| O(n!) | 10^35659 | 10^35643 years | 10^41678× work | Brute-force travelling salesman, all permutations |
Colour is a rough triage: green finishes in under a millisecond, blue under a second, amber under a minute, red beyond that. Big-O deliberately discards constant factors, so read these as orders of magnitude. Below about a thousand elements the constants usually decide the winner, which is why an O(n²) insertion sort beats a fancier algorithm on small arrays and why real sort implementations switch to it near the leaves.
How big can n get?
The largest input each complexity class clears inside a fixed time budget, at the machine speed you selected.
| Complexity | 1 second | 1 minute | 1 hour | 1 day |
|---|---|---|---|---|
| O(1) | No practical limit | No practical limit | No practical limit | No practical limit |
| O(log n) | No practical limit | No practical limit | No practical limit | No practical limit |
| O(√n) | 1.0 × 10^18 | 3.6 × 10^21 | 1.3 × 10^25 | 7.5 × 10^27 |
| O(n) | 1,000,000,000 | 60,000,000,000 | 3,600,000,000,000 | 86,400,000,000,000 |
| O(n log n) | 39,620,077 | 1,944,470,450 | 98,574,774,544 | 2,110,372,739,876 |
| O(n²) | 31,622 | 244,948 | 1,897,366 | 9,295,160 |
| O(n³) | 1,000 | 3,914 | 15,326 | 44,208 |
| O(2ⁿ) | 29 | 35 | 41 | 46 |
| O(n!) | 12 | 13 | 15 | 16 |
The two bottom rows are the reason exact algorithms get abandoned rather than optimised. Buying a machine a thousand times faster moves O(2ⁿ) forward by about ten in n, and moves O(n!) forward by about three. When the growth is that steep, hardware stops being the answer and the problem gets restated: an approximation, a heuristic, a branch-and-bound search, or a constraint that shrinks n itself.
The practical reading of this table: O(n log n) is the ceiling you should design toward for anything that touches a full dataset, O(n²) is acceptable when you can prove n stays small and are willing to defend that assumption in review, and anything exponential needs a different problem statement rather than a faster implementation.
Key takeaways
- Big-O describes how the number of operations grows with input size, not how long code takes on a particular machine; multiplying by operations per second is what turns it into a runtime.
- The practical wall for O(n²) is around 100,000 elements, where it needs about ten billion operations, while O(n log n) handles hundreds of millions comfortably.
- O(2^n) becomes intractable at roughly n = 50 and O(n!) at roughly n = 20, which is why exact solutions to those problems get replaced with heuristics rather than faster hardware.
- Doubling the input doubles the work for O(n), quadruples it for O(n²), and squares it for O(2^n), which is the difference between a slow feature and one that never returns.
- Constant factors matter below roughly a thousand elements, where an O(n²) algorithm with a tight inner loop routinely beats an O(n log n) one with allocation overhead.
Frequently asked questions
- How do you convert Big-O into an actual runtime?
- Evaluate the complexity function at your input size to get an operation count, then divide by how many operations per second your machine performs. An O(n²) algorithm on 10,000 elements is 100 million operations, which at roughly a billion simple operations per second is about a tenth of a second. Big-O deliberately drops constant factors, so treat the result as an order of magnitude rather than a measurement.
- At what input size does O(n²) become a problem?
- Around 100,000 elements. At that size an O(n²) algorithm needs ten billion operations, which is roughly ten seconds of pure computation and far worse once memory access patterns are involved. Below about 10,000 elements O(n²) is usually fine, and below about 1,000 it is often the fastest option because the constant factors are small.
- What operations-per-second value should I use?
- About one billion for simple operations on one core of a modern CPU, which assumes cache-friendly work like integer arithmetic on a contiguous array. Drop to ten million or lower if each "operation" involves a hash lookup, a pointer chase into cold memory, or an allocation, and drop far lower still if it involves any disk or network access.
- Why is O(n log n) considered the practical limit for sorting?
- Because any comparison-based sort must distinguish between n factorial possible orderings, and information theory puts a lower bound of n log n comparisons on doing so. Sorts that beat it, such as counting sort and radix sort, do so by not comparing elements at all, which only works when the keys have exploitable structure like a bounded integer range.
- Does Big-O account for memory?
- Not by default, but the same notation is used for space complexity and the trade-off between the two is constant in practice. An algorithm that is O(n) in time and O(n) in space can be worse in reality than an O(n log n) time, O(1) space one, because the memory version falls out of cache and the effective operations-per-second figure collapses.