CalcOpenly
English

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.

Drafted with AI writing toolsUpdated Checked examples: 6

= 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
Log₁₀ of the operation count
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, the O(n log n) growth model gives about 9,966 operations, which takes 9.966 µs at 1,000,000,000 operations per second. Curves are clipped at the top of the chart; this does not by itself identify a complexity class.

Growth on a log scale (zero counts omitted)

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 Rows: 8
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 s−1=0.000009966 st = \frac{9{,}965.784}{1{,}000{,}000{,}000\ \text{s}^{-1}} = 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.

In the formula, r is operations per second. Read the times as orders of magnitude: real code adds constant factors, cache effects and lower-order terms that Big-O leaves out.

How to estimate running time from Big-O

Evaluate the growth function at your input size, then divide by the number of simple operations the machine does per second: t = f(n) ÷ r. At n = 1,000 and 10⁹ operations per second, n log₂ n is about 9,966 operations, roughly 10 µs, and n² is 1,000,000 operations, or 1 ms. Use it to compare approaches before writing code.

What Big-O measures

NIST's definition says f(n) is O(g(n)) when some constant multiple of g(n) bounds f(n) from above for every n past some point. It describes growth, so constant factors and lower-order terms drop out.

So n² + 1,000n is O(n²). At n = 1,000 the extra term doubles the work, 2 million operations instead of 1 million, but at n = 1,000,000 it adds only 0.1%.

A bound also belongs to a case. Quicksort is O(n²) in the worst case and O(n log n) on average, and a hash-table lookup is O(1) on average but O(n) in the worst case.

Every class at n = 1,000

At 10⁹ operations per second:

  • O(1): 1 operation, 1 ns
  • O(log n): 9.97 operations, about 10 ns
  • O(n): 1,000 operations, 1 µs
  • O(n log n): 9,966 operations, about 10 µs
  • O(n²): 1,000,000 operations, 1 ms
  • O(n³): 10⁹ operations, 1 s
  • O(2ⁿ): 1.07 × 10³⁰¹ operations, 3.4 × 10²⁸⁴ years
  • O(n!): 4.02 × 10²⁵⁶⁷ operations, 1.3 × 10²⁵⁵¹ years

Doubling n adds one operation to log₂ n, doubles n, slightly more than doubles n log₂ n, multiplies n² by 4 and n³ by 8, and squares 2ⁿ.

How large can n be in one second?

At 10⁹ simple operations per second, one second of work covers:

  • O(n): n up to 1,000,000,000
  • O(n log n): about 39,600,000
  • O(n²): about 31,600
  • O(n³): 1,000
  • O(2ⁿ): 29
  • O(n!): 12

These limits explain why code that is instant on test data can stall in production. An O(n²) step that takes 1 ms on 1,000 items needs 10¹² operations, about 16.7 minutes, on 1,000,000.

Five worked estimates

ScenarioModel operationsModel time
Default9965.789.966 µs
Quadratic thousand1.00000E+61 ms
Exponential hundred1.26765E+304.017 × 10¹³ years
Twenty factorial2.43290E+1877.1 years
One logarithm00 s

Every row assumes 10⁹ operations per second. Default is n log₂ n and Quadratic thousand is n², both at n = 1,000. The other rows are 2ⁿ at n = 100, 20! and log₂ 1, which is zero. E+30 means × 10³⁰.

Choosing the operation rate

The 10⁹ figure fits simple CPU steps, such as comparisons in a tight loop. If one operation is a database query or a network request, measure instead: a loop that finishes 1 million operations in 2 seconds runs at 500,000 per second.

A faster machine divides every time by the same factor and leaves the operation counts alone. Ten times the speed barely helps exponential work: at 10¹⁰ operations per second, 2ⁿ still stops at n = 33 within one second.

Big-O mistakes to avoid

  • Judging by small inputs. Constant factors dominate small n, so an O(n²) insertion sort can beat an O(n log n) sort on a few dozen items. Timsort, behind Python's sorted(), uses insertion sort on short runs for this reason.
  • Calling every input n. Nested loops over two lists of sizes n and m are O(n·m), and a graph search is O(V + E). A single n hides which input drives the cost.
  • Worrying about the log base. log₂ n = 3.32 × log₁₀ n, a constant factor, so Big-O leaves the base out. The times here use base 2, the halving count of binary search.
  • Counting only arithmetic. Memory allocation, cache misses and I/O can cost more than the operations Big-O counts. Profile the real code before trusting a model.

When the bottleneck is moving data, the bandwidth calculator estimates transfer time.

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: Independent calculation

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: Independent calculation

2ⁿ at n = 100

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

Checked against: Independent calculation

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: Independent calculation

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.

About this calculator

t=f(n)rf∈{1,log⁡2n,n,nlog⁡2n,n2,n3,2n,n!}\begin{aligned} t &= \frac{f(n)}{r} \\ 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

This calculator includes 6 worked examples with independently sourced answers. They run in the test suite, and you can run them here too.

Put this calculator on your site

Paste this where you want the calculator to appear. It is free to use, it stays in step with corrections made here, and the credit line below it links back so your readers can find the full version.

Height
Preview the embed

Keep the credit line. It is the only condition, and it is what keeps these calculators free.

Related calculators