Big-O Growth Rate Calculator
Inputs
| Input size n | 20 |
|---|
Big-O Growth Rate Calculator
Enter an input size n to compare how many operations each common time complexity class requires — from O(log n) to O(n!).
Inputs
Input Size
Results
Enter a value to see results.
Common Complexities
Extreme Growth
Big-O Growth Rate
Big-O notation classifies how an algorithm's resource demand scales with input size. Rather than measuring seconds on a particular machine, it captures the shape of growth — does the work double when n doubles, or does it quadruple? The six complexities below are the ones you encounter most often in textbooks and interviews.
The six common classes
O(log n) — Logarithmic. Each step eliminates a constant fraction of the remaining work. Binary search on a sorted array of one billion elements takes only 30 comparisons because it halves the search space at every step. Balanced BST lookups and many divide-and-conquer recurrences fall here.
O(n) — Linear. Work grows in direct proportion to input size. Scanning an array once to find its maximum, counting characters in a string, or reading every element from a list are all linear. Linear algorithms are generally considered efficient.
O(n log n) — Linearithmic. The most common complexity for sorting. Merge sort, heapsort, and Timsort (used in Python and Java) all achieve O(n log n), which is also the theoretical lower bound for comparison-based sorting. At , this is roughly twenty million operations — fast in practice.
O(n²) — Quadratic. Two nested loops over the input. Bubble sort, insertion sort, and the naive matrix multiplication all have worst-case O(n²). At , that is one hundred million operations; at it becomes a trillion — impractical for large data.
O(2ⁿ) — Exponential. Work doubles with every additional element. The naive recursive Fibonacci algorithm recomputes subproblems exponentially; brute-force enumeration of all subsets of a set also grows as . At n = 40 the count exceeds one trillion.
O(n!) — Factorial. The fastest-growing class in everyday algorithm analysis. Brute-force solutions to permutation problems — listing every possible tour in the Travelling Salesman Problem — do one operation per permutation, and there are permutations in total. At n = 20, the count exceeds two quintillion operations.
Worked example at n = 20
The ratio between O(n log n) and O(n!) at n = 20 is roughly — the difference between a quick sort and waiting longer than the age of the universe.
Practical guidance
Constants and cache effects matter at small n; complexity dominates at large n. A threshold of roughly n = 10,000 is where O(n²) starts becoming uncomfortable on modern hardware (assuming simple operations). Beyond n = 10^6, you generally need an O(n log n) or better algorithm. Exponential and factorial algorithms require approximations, dynamic programming, or pruning strategies for any real-world input.
Number Base Converter is useful when working with binary representations of the input space.
Frequently Asked Questions (FAQ)
What does Big-O notation actually measure?
Big-O notation describes the upper bound on how an algorithm's running time (or memory use) grows as the input size n increases. It deliberately ignores constant factors and lower-order terms because those matter less as n grows large. An O(n²) algorithm will always overtake an O(n log n) algorithm for large enough inputs, regardless of hardware speed. Big-O is a tool for comparing algorithm designs — not a precise prediction of wall-clock time.
Why is the logarithm base 2?
Most divide-and-conquer algorithms (binary search, merge sort, balanced BSTs) split their work in half at each step, so the depth of that splitting is log₂ n. In Big-O analysis the base of the logarithm is just a constant factor and does not change the complexity class — log₂ n and log₁₀ n differ only by a constant — but base 2 is conventional in computer science because of binary splitting. This calculator uses base 2 to match that convention.
At what input size does complexity start to matter?
For small inputs, say n < 50, a well-tuned O(n²) algorithm often outperforms a theoretically faster O(n log n) one because it has lower constant overhead and better cache behaviour. Complexity starts to dominate once n reaches the hundreds or thousands.
At n = 1,000, an O(n log n) sort does about 10,000 comparisons while an O(n²) sort does 1,000,000. At n = 1,000,000 the gap is a billion to one trillion — complexity has become the only thing that matters.
Is O(n!) ever used in practice?
O(n!) algorithms are impractical for all but the smallest inputs. At n = 20, n! exceeds two quintillion operations — well beyond what any computer can finish in a human lifetime.
In practice, NP-hard problems like the Travelling Salesman Problem are solved with approximation algorithms, heuristics, or dynamic programming that avoid enumerating all permutations. The factorial column in this calculator serves as a reminder of why those approximation techniques exist.