Big O Calculator
Identify the complexity class implied by measured runtimes at two input sizes.
About Big O Calculator
Taking the log ratio of runtimes over the log ratio of sizes recovers the exponent empirically. An exponent near one indicates linear behaviour and near two indicates quadratic. Measuring the exponent from real timings catches accidental quadratic behaviour that code review often misses, such as a lookup inside a loop.
Formula
Big O
Exponent = log(runtime ratio) ÷ log(size ratio)
- growth exponent
- The power of n that best fits the two measurements
Worked example
With the default values below, Big O Calculator returns Inferred Complexity Class of O(n squared) quadratic. Change any input above and every figure here is recalculated in your browser.
Inputs used
- First input sizeminimum 1
- 1,000
- Runtime at the first sizeminimum 0 ms
- 12 ms
- Second input sizeminimum 1
- 10,000
- Runtime at the second sizeminimum 0 ms
- 1,450 ms
Results
- Inferred Complexity Class
- O(n squared) quadratic
- Measured Growth Exponent
- 2.0822
- Input Size Ratio
- 10.000
- Runtime Ratio
- 120.833
- Projected Runtime at Ten Times the Larger Size
- 175,208.33 ms
Step by step
- 1Values used
- 2Big O
- 3Inferred Complexity Class= O(n squared) quadratic
- 4Measured Growth Exponent= 2.0822
- 5Input Size Ratio= 10.000
- 6Runtime Ratio= 120.833
- 7Projected Runtime at Ten Times the Larger Size= 175,208.33 ms
Assumptions and limits
- The result is derived only from the 4 inputs listed above. Anything not among them is not part of the calculation.
- In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
- Figures are rounded for display to 4 decimal places, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.
How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.
Frequently Asked Questions
How is Big O calculated?
Exponent = log(runtime ratio) ÷ log(size ratio) Taking the log ratio of runtimes over the log ratio of sizes recovers the exponent empirically. An exponent near one indicates linear behaviour and near two indicates quadratic.
Why does Big O matter?
Measuring the exponent from real timings catches accidental quadratic behaviour that code review often misses, such as a lookup inside a loop.
What values do I need to enter?
This calculator takes 4 inputs: First input size, Runtime at the first size, Second input size, Runtime at the second size. The pre-filled defaults are a realistic starting point — replace them with figures from your own environment for a result you can act on.