How to use the Algorithm Complexity
- Enter the input size n you expect at realistic scale.
- Select the complexity class of your algorithm.
- Compare the operation count against other classes.
- Estimate wall-clock time by dividing by a plausible operations-per-second figure.
How the calculation works
Complexity classes rank by growth rate: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential and O(n!) factorial. Constants and lower-order terms are dropped because they stop mattering as n grows — 3n² + 500n is O(n²), since past a certain size the squared term dominates everything else.
The practical consequence is a cliff, not a slope. At n = 1,000 a quadratic algorithm needs a million operations, which is instant; at n = 1,000,000 it needs a trillion, which is hours. That is why sorting is O(n log n) and hash lookups are O(1) — the classes are chosen so that ten times the data does not mean a hundred times the work. For small n, constants genuinely do decide the winner, which is why real sort implementations switch to insertion sort under a threshold.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)Source: Standard asymptotic analysis (Big O notation) as defined in Cormen et al., Introduction to Algorithms.
Worked example
Comparing an O(n²) nested loop with an O(n log n) sort at n = 250,000.
- O(n²) = 250,000² = 6.25 × 10¹⁰ operations.
- O(n log n) = 250,000 × log₂(250,000) ≈ 250,000 × 18 = 4.5 × 10⁶.
- Ratio ≈ 13,900×.
- At 10⁸ ops/second: 625 seconds versus 0.045 seconds.
Ten minutes versus a twentieth of a second — the same task, one algorithmic choice apart.
Frequently asked questions
Does Big O tell me actual runtime?+
No. It describes growth. A high-constant O(n) routine can be slower than a lean O(n log n) one at small sizes.
Why drop constants?+
Because they do not change the growth curve, which is what determines whether the algorithm survives scaling.
What about space complexity?+
The same notation applied to memory. An in-place sort is O(1) auxiliary space; merge sort is O(n).
Is O(n log n) the best possible for sorting?+
For comparison-based sorting, yes. Counting and radix sorts beat it by exploiting key structure instead of comparisons.
Last reviewed August 31, 2026. We review this page whenever the underlying formula, tax year, published rate or standard changes.