How to use the algorithm growth calculator
- Enter an input size n, a whole number from 2 up to a billion.
- Enter how many basic steps per second your machine can run. The default of 1,000,000,000 is an example you can change.
- Read the table of steps and time for seven growth rates, from log n to n factorial.
- Change n to see which rates stay small and which run away.
Formula
steps = log2 n, n, n x log2 n, n^2, n^3, 2^n, n!
time = steps / steps per second
n! for large n uses log10(n!) from Stirling's series
Each row counts steps for a program whose running time equals that formula exactly, with a constant of 1. Counts are exact whole numbers when they are small, and are shown as a number times a power of ten when large.
Small and medium sizes
For n = 10 the step counts are 3.32, 10, 33.22, 100, 1,000, 1,024 and 3,628,800. At a billion steps a second, all of them finish in well under a second. For n = 1,000, n log n is 9,966 steps (about 10 microseconds), n squared is 1,000,000 steps (1 millisecond) and n cubed is a billion steps (1 second).
For n = 60, n squared is only 3,600 steps, but 2^60 is 1.15 x 10^18 steps, about 36.53 years at the same speed, and 60 factorial is 8.32 x 10^81 steps, about 2.64 x 10^65 years. At n = 1,000, 2^1000 needs 1.07 x 10^301 steps.
Why growth rate beats speed
A machine ten times faster cuts every time by a factor of ten, which helps a polynomial algorithm a lot and an exponential one hardly at all. Adding one to n doubles a 2^n step count, so a faster machine buys only a few extra items. That is why the shape of the growth matters more than the constant in front of it once n is large.
How to read the table
Treat the table as a map of what is feasible. Rows that stay under a second are comfortable, rows measured in hours need thought, and rows measured in years are out of reach whatever the hardware. Real programs have constants and lower-order terms, and cache, memory and input shape change the speed, so use the numbers to compare shapes rather than to predict a timing. For related developer tools see the CRC Calculator and the Exponential Backoff Schedule Generator.
Assumptions and limits
- The speed is one number of identical steps per second.
- A constant of 1 and no lower-order terms are used for every row.
- Very large 2^n and n! values come from logarithms and are shown to three significant digits.
- A year is 365.25 days.
Frequently asked questions
What does log2 n mean here?
It is the number of times n can be halved before reaching 1, as in binary search. The row shows the exact value, such as 3.32 for n = 10.
Why is n log n listed separately from n squared?
Good sorting methods run in about n log n steps, while simple ones take n squared. For n = 1,000,000, one needs about 20 million steps and the other a trillion.
Why does the factorial row show a power of ten?
The exact value has too many digits to read. For large n the page shows the leading digits and the exponent, which is what matters for comparing sizes.
Can I use this to time my code?
Not exactly. Real running time depends on constants, memory and the data. The table shows how time grows with n, which tells you whether a method can scale.