Big-O Growth Calculator (operations for n)

Understanding the Big-O growth calculator — concept and principle

Big-O notation describes how the work of an algorithm grows as the input size n grows. This calculator turns six common growth classes into concrete operation counts for your n and converts them into wall-clock time at a chosen speed, so you can see at a glance which algorithms stay practical and which explode.

How it is calculated

• Operation counts: log₂ n, n, n·log₂ n, n², n³ and 2ⁿ.
• Time ≈ operations ÷ operations per second.
• The time is shown in µs, ms, s, days or years depending on size; 2ⁿ is reported as "astronomical" when n exceeds 1,000.

Constant factors and lower-order terms are ignored, exactly as in Big-O itself.

The principle

Big-O keeps only the fastest-growing term because, for large n, it dominates everything else. Doubling n adds one step to a log n algorithm, doubles an O(n) one, multiplies O(n²) by four and O(n³) by eight, and squares the work of O(2ⁿ). The speed figure of 10⁹ simple operations per second is a rough order of magnitude for one modern CPU core; real code may do far fewer useful operations per second because of memory access, branching and language overhead.

Worked example

1. Inputs: n = 1,000,000, speed = 10⁹ operations per second.
2. O(log n): log₂ 10⁶ ≈ 19.93 operations → 19.93 ÷ 10⁹ s ≈ 0.0199 µs.
3. O(n): 10⁶ operations → 1 ms.
4. O(n log n): 10⁶ × 19.93 ≈ 19,930,000 operations → 19.9 ms.
5. O(n²): 10¹² operations → 1,000 s (about 17 minutes).
6. O(n³): 10¹⁸ operations → 10⁹ s ÷ (86,400 × 365.25) ≈ 31.7 years.
7. O(2ⁿ): n is far above 1,000, so the result is astronomical.

How to read the result

For interactive work aim for well under a second. With n = 10⁶, any O(n) or O(n log n) method is comfortable, O(n²) is already too slow for a request and O(n³) is hopeless. A useful rule of thumb at 10⁸–10⁹ simple steps per second: O(n²) is fine up to roughly n = 10⁴, O(n³) up to a few hundred, and O(2ⁿ) only to about n = 30.

Common mistakes

• Treating Big-O as exact timing; an O(n log n) routine with a large constant can lose to an O(n²) one for small n.
• Forgetting that Big-O is usually a worst-case or average-case statement and the two can differ (quicksort is O(n log n) on average but O(n²) worst case).
• Using the CPU clock rate as the operation rate; one line of code is many machine instructions.

Frequently asked questions

Which logarithm base does Big-O use?

It does not matter: log₂ n and log₁₀ n differ only by a constant factor, which Big-O ignores. The calculator uses base 2 because halving is the usual cause.

Is O(n log n) much slower than O(n)?

Only by a factor of log₂ n, about 20 for a million items and 30 for a billion, which is why sorting is rarely the bottleneck.

What is the difference between O, Θ and Ω?

O is an upper bound, Ω a lower bound and Θ a tight bound that holds in both directions.

Sources: D. E. Knuth, "Big Omicron and Big Omega and Big Theta", SIGACT News 8(2), 1976 · T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press (growth of functions)