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

交互版本：https://www.calcopenly.com/zh/programming/big-o-growth-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.

## 输入

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

## 结果

- Running time in seconds (s)
- Running time — 主要结果
- Operations
- Digits of the operation count (log₁₀)

## 公式

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

## 计算示例

### 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**
- 核验来源：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**
- 核验来源：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**
- 核验来源：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**
- 核验来源：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**
- 核验来源：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**
- 核验来源：Python 3.8: math.lgamma(1000001) / math.log(10) = 5565708.917186718 (10⁶! has 5,565,709 digits)

## 常见问题

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

### “Big-O time complexity calculator”有多准确？

准确性取决于输入值和方法的假设。十进制运算使用50位有效数字，但估算、数值方法和源数据的精度可能较低；显示时的舍入并不能消除这些限制。 已按独立来源核验的计算示例：6。 例如，“n² at n = 1,000”根据Python 3.8: 1000**2 / 1e9 = 0.001进行核验。

### 这种方法出自哪里？

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.

## 来源

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