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

Version interactive : https://www.calcopenly.com/fr/programming/big-o-growth-calculator
Sujet : Calculatrices de programmation et de technologie

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.

## Données

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

## Résultats

- Running time in seconds (s)
- Running time — résultat principal
- Operations
- Digits of the operation count (log₁₀)

## Formule

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

## Exemples détaillés

### 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**
- Source de vérification : 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**
- Source de vérification : 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**
- Source de vérification : 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**
- Source de vérification : 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**
- Source de vérification : 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**
- Source de vérification : 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.

### Quelle est la précision de « Big-O time complexity calculator » ?

La précision dépend de vos données et des hypothèses de la méthode. Le calcul décimal utilise 50 chiffres significatifs, mais les estimations, méthodes numériques et données sources peuvent être moins précises ; l’arrondi affiché ne supprime pas ces limites. Exemples résolus vérifiés à partir de sources indépendantes : 6. Par exemple, « n² at n = 1,000 » est vérifié à l’aide de Python 3.8: 1000**2 / 1e9 = 0.001.

### D’où vient cette méthode ?

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)