# 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.

Interactive version: https://www.calcopenly.com/programming/big-o-growth-calculator
Subject: Programming and tech calculators

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.

## Inputs

- **Input size n**
- **Operations per second**: A modern CPU core does very roughly 10⁹ simple operations per second.
- **Your algorithm** (options: O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!))

## Results

- Running time in seconds (s)
- Running time — main result
- Operations
- Digits of the operation count (log₁₀)

## Formula

$$
\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}
$$

## 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

### log n at n = 1 is zero work (edge)

- Input size n: 1
- Operations per second: 1e9
- Your algorithm: O(log n)
- **Operations: 0**
- **Running time in seconds: 0 s**
- **Running time: 0 s**
- Checked against: log₂ 1 = 0 by definition

### Digits of one million factorial

- Input size n: 1,000,000
- Operations per second: 1e9
- Your algorithm: O(n!)
- **Digits of the operation count (log₁₀): 5,565,708.9172**
- Checked against: Python 3.8: math.lgamma(1000001) / math.log(10) = 5565708.917186718 (10⁶! has 5,565,709 digits)

## 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.

## Sources

- 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](https://doi.org/10.1145/1008328.1008329)