CalcOpenly

Big-O time complexity calculator

Operation counts and running times for O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ) and O(n!) at your input size, on a log-scale chart.

Updated Checked against 6 worked examples

= 1,000,000,000
A modern CPU core does very roughly 10⁹ simple operations per second.
Try
Running time
9.966 µs
Running time: 9.966 µs
Running time in seconds
0.000009966s
Operations
9,965.78
Digits of the operation count (log₁₀)
3.9985
Big-O drops constant factors and lower-order terms, so real running times can differ by a constant multiple.

At n = 1,000, an O(n log n) algorithm does about 9,966 operations, which takes 9.966 µs at 1,000,000,000 operations per second. Lines that leave the top of the chart grow faster than any polynomial.

Growth on a log scale

02.557.5102004006008001,000nlog₁₀ of operationsOne second of work
O(1)O(log n)O(n)O(n log n)O(n²)O(n³)O(2ⁿ)O(n!)
Every class at n = 1,000 (8 rows)
ClassOperationslog₁₀Time
O(1)101 ns
O(log n)9.96580.9999.966 ns
O(n)1,00031 µs
O(n log n)9,965.783.9999.966 µs
O(n²)1,000,00061 ms
O(n³)1,000,000,00091 s
O(2ⁿ)1.07151 × 10³⁰¹301.033.395 × 10²⁸⁴ years
O(n!)4.02387 × 10²⁵⁶⁷2,567.6051.275 × 10²⁵⁵¹ years
How it's calculated S

  1. Count the operations

    f(n)=nlog⁡2n=9,965.784(n=1000)f(n) = n \log_2 n = 9{,}965.784\quad (n = 1000)

    Logarithms are base 2 (halving or binary splitting); another base changes the count by a constant factor only.

  2. Divide by the machine speed

    t=9,965.7841,000,000,000 ops/s=0.000009966 st = \frac{9{,}965.784}{1{,}000{,}000{,}000\ \text{ops/s}} = 0.000009966\ \text{s}

  3. Express in everyday units

    9.966 µs

About the Big-O time complexity calculator

Big-O notation describes how an algorithm's work grows with the input size n, leaving out constant factors. The calculator evaluates each growth function f(n), namely 1, log2 n, n, n log2 n, n², n³, 2ⁿ and n!, at your n, then divides by the number of simple operations the machine does per second to estimate the running time.

It helps judge whether an approach will finish in time before you write it. At the default n = 1,000 and 10^9 operations per second, an O(n log n) sort does about 9,966 operations and takes about 10 µs, and O(n²) takes 1 ms, while O(2ⁿ) at only n = 100 would need 4.0 × 10^13 years.

Read the times as orders of magnitude: real code adds constant factors, cache effects and lower-order terms that Big-O leaves out.

Worked examples

n² at n = 1,000

Input size n
1000
Operations per second
1e9
Your algorithm
O(n²)
Operations
1,000,000
Running time in seconds
0.001 s
Running time
1 ms

Checked against: Python 3.8: 1000**2 / 1e9 = 0.001

n log n at n = 1,000

Input size n
1000
Operations per second
1e9
Your algorithm
O(n log n)
Operations
9,965.78
Running time in seconds
0.000009966 s

Checked against: Python 3.8 decimal, 50 digits: Decimal(1000) * Decimal(1000).ln() / Decimal(2).ln() = 9965.78428466208704…

2ⁿ at n = 100

Input size n
100
Operations per second
1e9
Your algorithm
O(2ⁿ)
Operations
1.26765 × 10³⁰
Digits of the operation count (log₁₀)
30.1030
Running time
4.017 × 10¹³ years

Checked against: Python 3.8: 2**100 = 1267650600228229401496703205376; 2**100 / 1e9 / 31556952 = 4.0170e13 years

20! operations

Input size n
20
Operations per second
1e9
Your algorithm
O(n!)
Operations
2.4329 × 10¹⁸
Running time in seconds
2,433,000,000 s

Checked against: Python 3.8: math.factorial(20) = 2432902008176640000

Questions

What is the difference between O(n log n) and O(n²)?

At n = 1,000, n log2 n is about 9,966 while n² is 1,000,000, roughly 100 times more; at n = 1 million the gap is about 50,000 times (2 × 10^7 against 10^12). That is why merge sort and heapsort, which are O(n log n), beat insertion sort and bubble sort, which are O(n²) in the worst case, on anything but small inputs.

What does O(log n) mean?

O(log n) means the work grows with the logarithm of the input size, usually because each step halves what is left, as in binary search. Doubling n adds only one step: a sorted list of 1,000 items needs about 10 comparisons (log2 1,000 ≈ 9.97), and 1 million items about 20. The base of the logarithm changes only a constant factor, so the notation leaves it out.

Why are O(2ⁿ) and O(n!) algorithms impractical?

Their work multiplies with each extra item. 2ⁿ doubles whenever n grows by 1, so at n = 100 it is about 1.27 × 10^30 operations, or 4.0 × 10^13 years at 10^9 per second, roughly 2,900 times the age of the universe. n! grows faster still: 20! is already 2.43 × 10^18, about 77 years of work. Brute-force searches over all subsets or orderings fall into these classes.

Does Big-O give the actual running time?

No. Big-O bounds how work grows as n increases and drops constant factors and lower-order terms, so 3n² + 100n and n²/2 are both O(n²). Two O(n) algorithms can differ severalfold in speed, and for small n an O(n²) method can beat an O(n log n) one. Use the times here as orders of magnitude, then measure real code with a profiler.

What is the difference between Big-O, Big-Omega and Big-Theta?

Big-O is an asymptotic upper bound, Big-Omega (Ω) a lower bound, and Big-Theta (Θ) both at once, a tight bound. Merge sort is Θ(n log n) on every input, while insertion sort is O(n²) in the worst case and takes only n − 1 comparisons on already sorted input. Knuth set out these definitions in SIGACT News in 1976, and CLRS chapter 3 follows them.

How accurate is the Big-O time complexity calculator?

Accuracy depends on your inputs and the method's assumptions. Decimal arithmetic uses 50 significant digits, but estimates, numerical methods and source data can be less precise; the displayed rounding does not remove those limits. It is checked against 6 worked examples whose answers come from independent sources; for example, “n² at n = 1,000” is checked against Python 3.8: 1000**2 / 1e9 = 0.001.

Where does the method come from?

Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4th ed., ch. 3 (asymptotic notation); Knuth, “Big Omicron and big Omega and big Theta”, SIGACT News 8(2), 1976.

About this calculator

t=f(n)operations per secondf∈{1,log⁡2n,n,nlog⁡2n,n2,n3,2n,n!}\begin{aligned} t &= \frac{f(n)}{\text{operations per second}} \\ f &\in \{1, \log_2 n, n, n\log_2 n, \\ &\qquad n^2, n^3, 2^n, n!\}\end{aligned}

Sources

  1. Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4th ed., ch. 3 (asymptotic notation)
  2. Knuth, “Big Omicron and big Omega and big Theta”, SIGACT News 8(2), 1976

Checked against references

6 worked examples with independently sourced answers ship with this calculator. They run in the test suite; you can run them here too.

Related calculators

Allow optional Google Analytics to measure page visits? Calculators work either way. Privacy and choices

Optional analytics: off.