Time Complexity Calculator
The Same Algorithm, a Thousand Times Larger Input
Big-O notation describes how an algorithm's workload grows as its input grows, but the abstract expression alone — "n squared," "n log n" — doesn't convey how brutal that growth actually feels at real input sizes. An O(n²) algorithm and an O(n log n) algorithm can both look fine at n = 10, then diverge into "instant" versus "unusable" by n = 1,000,000. This calculator turns a complexity class and an input size into an estimated operation count and wall-clock time, so the difference is a concrete number instead of an abstraction.
The Formula
Each complexity class maps to an operation-count formula, which is then divided by an assumed processing rate:
O(1)=1, O(log n)=log&sub2;(n), O(n)=n, O(n log n)=n×log&sub2;(n),
O(n²)=n², O(n³)=n³, O(2ⁿ)=2ⁿ, O(n!)=n!
Time = Operations / Operations per Second
The default rate is 1,000,000,000 operations per second (a rough proxy for a modern CPU core), but you can override it to model a slower or faster environment.
Where This Calculation Matters
- Algorithm selection — deciding whether an O(n²) sort is acceptable for a dataset of a given size, or whether an O(n log n) alternative is worth the added complexity.
- Interview and coursework prep — building intuition for why "it's just one more nested loop" can turn a fast algorithm into an impractical one.
- Capacity and scaling estimates — projecting how a system's processing time will grow as user count or dataset size increases tenfold.
- Recognizing intractable problems — spotting when a brute-force O(2ⁿ) or O(n!) approach will never finish for realistic input sizes, well before it's run.
Estimated Time at n = 1,000 (1 billion ops/sec)
| Complexity | Operations | Estimated Time |
|---|---|---|
| O(1) | 1 | < 0.01 microsec |
| O(log n) | ~10 | 0.01 microsec |
| O(n) | 1,000 | 1.00 microsec |
| O(n log n) | ~9,966 | 9.97 microsec |
| O(n²) | 1,000,000 | 1.00 millisec |
| O(n³) | 1,000,000,000 | 1.0 sec |
O(2ⁿ) and O(n!) grow so fast that even n = 30 (2ⁿ ≈ 1.07 billion ops, ~1.07 sec) or n = 15 (n! ≈ 1.3 trillion ops, ~21.8 min) already outpaces O(n³) at n = 1,000 — this calculator caps O(2ⁿ) at n ≤ 1000 and O(n!) at n ≤ 170 to avoid numeric overflow.
How to Use This Calculator
- Choose a Time Complexity class from O(1) up through O(n!).
- Enter n (input size), the number of elements or operations the algorithm processes.
- Optionally set Operations per Second to model a specific machine's throughput (defaults to 1,000,000,000).
- Select Calculate to see the estimated operation count and the corresponding wall-clock time.
Related Calculations
Working through bit-level logic that underlies many algorithms? Try the Binary Calculator. For a more networking-flavored throughput question, see the Bandwidth Calculator.