In computer science and software engineering, algorithm efficiency is not measured in seconds on a specific machine. Processor clock speeds, memory bandwidth, compiler optimizations, and background processes vary from run to run. Instead, computer scientists evaluate algorithms by their asymptotic time and space complexity using Big-O notation.
Big-O describes how the execution count of an algorithm scales as the input size n approaches infinity. An algorithm with a lower growth rate will inevitably outperform an algorithm with a higher growth rate once n is sufficiently large, regardless of how much hardware power you throw at it.
Yet in academic coursework (such as CS 61B, MIT 6.1210, or algorithm technical interviews), students often memorize the growth hierarchy without appreciating the staggering quantitative differences between complexity classes.
This guide evaluates the seven fundamental Big-O growth functions:
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Below, we compute exact values at n = 10, n = 100, and n = 1,000 using ToolSphere's tested Big-O mathematics engine, illustrate where finite constants override asymptotic theory, and map each complexity class to real interactive tools on the site.
The Big-O Growth Rate Table (n = 10, 100, 1,000)
The table below lists the exact operations and symbolic values computed directly by ToolSphere's Big-O library (src/lib/algorithms/big-o.ts). Logarithms use base 2 (the standard convention in computer science), with decimal approximations rounded to two decimal places for readability.
| Complexity Class | Common Name | n = 10 | n = 100 | n = 1,000 | Practical Feasibility |
|---|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 | Instantaneous at any scale |
| O(log n) | Logarithmic | log₂(10) ≈ 3.32 | log₂(100) ≈ 6.64 | log₂(1000) ≈ 9.97 | Virtually instantaneous |
| O(n) | Linear | 10 | 100 | 1,000 | Fast; scales proportionally |
| O(n log n) | Linearithmic | 10 × log₂(10) ≈ 33.22 | 100 × log₂(100) ≈ 664.39 | 1000 × log₂(1000) ≈ 9,965.78 | Optimal for comparison sorting |
| O(n²) | Quadratic | 100 | 10,000 | 1,000,000 (10⁶) | Noticeable delay past n = 10,000 |
| O(2ⁿ) | Exponential | 1,024 | 1.27 × 10³⁰ (31 digits) | 1.07 × 10³⁰¹ (302 digits) | Infeasible past n = 40–50 |
| O(n!) | Factorial | 3,628,800 | 9.33 × 10¹⁵⁷ (158 digits) | 4.02 × 10²⁵⁶⁷ (2,568 digits) | Infeasible past n = 12–15 |
Key Observations from the Exact Values
- Logarithmic efficiency: Increasing n by a factor of 100 (from 10 to 1,000) multiplies the input by 100x. An O(n) linear algorithm executes 100x more work (from 10 to 1,000). But an O(log n) algorithm requires only 6.65 additional operations (growing from 3.32 to 9.97).
- The sorting divergence: At n = 1,000, an O(n log n) algorithm requires 9,965.78 operations, whereas an O(n²) algorithm executes exactly 1,000,000 operations—a hundredfold difference. This divergence explains why Merge Sort or Quick Sort is required for large datasets rather than Bubble Sort or Insertion Sort.
- The combinatorial wall: At n = 100, an exponential O(2ⁿ) function generates 1,267,650,600,228,229,401,496,703,205,376 operations (31 digits). A processor executing one billion operations per second would require over 40 quintillion years to complete it. The factorial O(100!) function reaches 158 digits, exceeding the estimated number of fundamental particles in the observable universe (approximately 10⁸⁰) by 77 orders of magnitude.
Detailed Breakdown of the Seven Complexity Classes
1. O(1) — Constant Time
An algorithm runs in O(1) constant time when its execution count and resource consumption do not depend on the input size n. Regardless of whether the collection holds 10 items or 10 billion items, the operation completes in bounded, predictable steps.
- Exact values: 1 operation at n = 10, n = 100, and n = 1,000.
- Typical operations: Arithmetic calculations, reading a variable, pushing or popping from a stack, accessing an array element by its zero-based index
arr[i], and looking up a key in a well-balanced hash map. - Real-world example on ToolSphere: In the Hash Table Simulator, inserting or retrieving a key with separate chaining or linear probing operates in average-case O(1) time when the load factor remains bounded.
2. O(log n) — Logarithmic Time
An algorithm runs in O(log n) logarithmic time when each successive step cuts the remaining problem size by a constant fraction (typically by half). As n doubles, the algorithm executes only one additional step.
- Exact values:
- n = 10:
log₂(10)≈ 3.321928 (ceiling of 4 comparisons) - n = 100:
log₂(100)≈ 6.643856 (ceiling of 7 comparisons) - n = 1,000:
log₂(1000)≈ 9.965784 (ceiling of 10 comparisons)
- n = 10:
- Typical algorithms: Binary search on a sorted array, searching, inserting, or deleting in a self-balancing binary search tree, and finding the minimum in a binary heap.
- Real-world example on ToolSphere: In the Data Structure Visualizer, an AVL tree maintains a balance factor within
{-1, 0, +1}via tree rotations. Even when inserting keys in strictly ascending order, tree height never exceeds 1.44 × log₂(n), guaranteeing O(log n) lookup time.
3. O(n) — Linear Time
An algorithm runs in O(n) linear time when its runtime scales in direct 1:1 proportion to the size of the input. Processing ten times as many items requires ten times as much work.
- Exact values:
- n = 10: 10 operations
- n = 100: 100 operations
- n = 1,000: 1,000 operations
- Typical algorithms: Single-pass array traversals, finding the minimum or maximum element, counting occurrences, linear search, Breadth-First Search (BFS) and Depth-First Search (DFS) on trees or linear graphs, and string prefix searches.
- Real-world example on ToolSphere: In the Sorting Algorithm Visualizer, when given an array that is already sorted, both Bubble Sort (with an early-exit swap flag) and Insertion Sort detect the sorted condition and terminate after exactly n - 1 comparisons—a pure O(n) best-case execution.
4. O(n log n) — Linearithmic Time
An algorithm runs in O(n log n) linearithmic time (also called log-linear) when it divides a problem into subproblems logarithmically (log n levels) and performs linear work (O(n)) across all subproblems at each level. In computer science, Ω(n log n) is the mathematical lower bound for any general comparison-based sorting algorithm on n arbitrary elements.
- Exact values:
- n = 10:
10 × log₂(10)≈ 33.219281 - n = 100:
100 × log₂(100)≈ 664.385619 - n = 1,000:
1000 × log₂(1000)≈ 9,965.784285
- n = 10:
- Typical algorithms: Merge Sort, Heap Sort, average-case Quick Sort, Fast Fourier Transform (FFT), and divide-and-conquer recurrences of the form
T(n) = 2T(n/2) + n. - Real-world example on ToolSphere: You can solve the merge sort recurrence
T(n) = 2T(n/2) + nusing ToolSphere's Master Theorem Calculator. Because a = 2, b = 2, and the critical exponent log_b(a) = log₂(2) = 1 matches the degree of f(n) = n, Case 2 applies with k = 0, givingΘ(n log n). In the Sorting Algorithm Visualizer, Merge Sort consistently achieves this efficiency on reverse, random, and duplicate-heavy arrays.
5. O(n²) — Quadratic Time
An algorithm runs in O(n²) quadratic time when its execution count scales with the square of the input size. This commonly occurs when an algorithm performs nested iterations over an n-element dataset, comparing every element against every other element.
- Exact values:
- n = 10: 100 operations
- n = 100: 10,000 operations
- n = 1,000: 1,000,000 operations
- Typical algorithms: Elementary sorting algorithms in average and worst cases (Bubble Sort, Selection Sort, Insertion Sort), naive all-pairs distance checks, nested loop matrix addition, and worst-case Quick Sort (when partition pivots are chosen pathologically on pre-sorted data).
- Real-world example on ToolSphere: In the Sorting Algorithm Visualizer, Selection Sort on an array of length n always executes
n × (n - 1) / 2comparisons regardless of whether the array is already sorted, executing 45 comparisons for n = 10 and 4,950 comparisons for n = 100.
6. O(2ⁿ) — Exponential Time
An algorithm runs in O(2ⁿ) exponential time when each addition of a single item to the input doubles the total number of operations. Growth of this magnitude rapidly escapes practical computational feasibility.
- Exact values:
- n = 10: 1,024 operations
- n = 100:
1267650600228229401496703205376(31 digits) - n = 1,000: 302-digit integer starting
1071508607186...
- Typical algorithms: Brute-force subset generation (generating all 2ⁿ subsets of an n-element set), naive recursive Fibonacci without dynamic programming, and evaluating all possible variable assignments in Boolean Satisfiability (SAT).
- Real-world example on ToolSphere: In the Truth Table Generator, entering a Boolean formula with n distinct propositional variables produces a truth table with exactly 2ⁿ truth rows. A 4-variable formula yields 16 rows; an 8-variable formula yields 256 rows; an n = 10 formula requires 1,024 rows. Similarly, in the NFA to DFA Converter, the subset construction algorithm can theoretically produce up to 2ⁿ power-set states in the worst-case determinization of an n-state automaton.
7. O(n!) — Factorial Time
An algorithm runs in O(n!) factorial time when it examines every possible permutation of n distinct items. Factorial growth accelerates even faster than exponential growth because the multiplier itself increases with each step: n! = n × (n - 1) × (n - 2) × ... × 1.
- Exact values:
- n = 10: 3,628,800 operations
- n = 100: 158-digit integer starting
933262154439441... - n = 1,000: 2,568-digit integer starting
402387260077...
- Typical algorithms: Generating all permutations of an array, brute-force solutions to the Traveling Salesperson Problem (evaluating all (n - 1)! / 2 unique Hamiltonian cycles), and unconstrained brute-force combinatorial matching.
- Feasibility threshold: Modern computers can evaluate n = 10 in a few milliseconds (3.63 million steps), but n = 15 requires over 1.3 trillion steps, and n = 20 requires 2.43 × 10¹⁸ steps, which would take decades on a cluster of supercomputers.
When Constants Override Asymptotic Growth: The Crossover Point
Big-O notation deliberately strips away constant factors (c) and low-order terms because it characterizes behavior as n approaches infinity. However, for practical input sizes n, an algorithm with a higher asymptotic complexity can run faster than an algorithm with a lower asymptotic complexity if its constant factor is significantly smaller.
To demonstrate this mathematically, consider two competing algorithms:
- Algorithm A: An asymptotic linear algorithm with high per-element overhead:
Model A = 20 × n - Algorithm B: An asymptotic quadratic algorithm with minimal constant overhead:
Model B = 1 × n²
Using ToolSphere's Big-O comparison function (compareGrowth), we evaluate both models across a sweep of input sizes:
n = 10: Model A = 200 operations vs Model B = 100 operations --> Algorithm B wins (2x faster)
n = 16: Model A = 320 operations vs Model B = 256 operations --> Algorithm B wins
n = 20: Model A = 400 operations vs Model B = 400 operations --> Tie (Crossover point)
n = 32: Model A = 640 operations vs Model B = 1,024 operations --> Algorithm A wins
n = 100: Model A = 2,000 operations vs Model B = 10,000 operations --> Algorithm A wins (5x faster)
n = 1000: Model A = 20,000 operations vs Model B = 1,000,000 operations --> Algorithm A wins (50x faster)
The Engineering Takeaway: Hybrid Algorithms
This exact crossover dynamic explains real-world standard library design:
- Why Insertion Sort beats Merge Sort on small arrays: Merge sort incurs auxiliary array allocation and recursive call overhead (a large constant factor c). Insertion sort consists of a tight, cache-friendly loop with almost zero overhead. For small arrays (typically n ≤ 16 to 32), the quadratic algorithm executes fewer machine instructions than the linearithmic one.
- Production hybrid sorts: Production algorithms like Timsort (the default sorting algorithm in Python, Android, and Java SE) and Introsort (the standard sorting algorithm in C++
std::sort) partition large arrays using divide-and-conquer (Merge Sort or Quick Sort), but switch to Insertion Sort whenever a partition shrinks below 16 to 32 elements.
Interactive Exploration on ToolSphere
To model custom algorithm runtimes and compare growth curves visually, use ToolSphere's companion tools:
- Big-O Complexity Calculator:
- Enter any input size n up to 1,000.
- Assign custom constant multipliers to two competing models (for example, comparing 50 × n log₂ n against 2 × n²).
- View the winner verdict, exact operation counts, and a logarithmic scale chart showing where curves intersect.
- Sorting Algorithm Visualizer:
- Step through Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, and Heap Sort on identical arrays.
- Inspect the concrete pass counts, element comparisons, swaps, and memory writes to see how theoretical Big-O bounds translate into physical execution steps.
Frequently Asked Questions
What is the formal mathematical definition of Big-O?
An algorithm's runtime T(n) is in O(f(n)) if there exist positive constants c and n₀ such that for all n ≥ n₀:
0 ≤ T(n) ≤ c × f(n)
This establishes an asymptotic upper bound. It guarantees that for all inputs larger than n₀, the runtime of T(n) will not exceed c × f(n).
What is the difference between Big-O, Big-Omega, and Big-Theta?
- Big-O (O): Asymptotic upper bound (
T(n) ≤ c × f(n)). The algorithm will not perform worse than this. - Big-Omega (Ω): Asymptotic lower bound (
T(n) ≥ c × f(n)). The algorithm will require at least this much work. - Big-Theta (Θ): Asymptotically tight bound. The algorithm satisfies both
O(f(n))andΩ(f(n)), sandwiching the runtime within constant multiples off(n).
Why does the base of the logarithm not matter in Big-O?
In Big-O notation, logarithmic bases are interchangeable because of the change-of-base formula:
log_a(n) = log_b(n) / log_b(a)
Because 1 / log_b(a) is a constant multiplier, it is absorbed by the constant c in Big-O. Thus, O(log₂ n), O(ln n), and O(log₁₀ n) belong to the identical complexity class, written simply as O(log n). However, base 2 is preferred in computer science because binary trees and divide-and-conquer algorithms halve the input at each step.
Why is O(n log n) the lower bound for comparison sorting?
Any sorting algorithm that operates solely by comparing pairs of elements can be modeled as a binary decision tree. For an array of n items, there are n! possible permutations. To distinguish among all n! outcomes, the binary decision tree must have at least n! leaves. The minimum height of a binary tree with n! leaves is:
Height ≥ log₂(n!) = Θ(n log n)
Because the height corresponds to the worst-case number of comparisons, no comparison-based sort can beat Ω(n log n). Non-comparison sorts like Counting Sort or Radix Sort can achieve O(n) by exploiting key properties rather than pairwise comparisons.
Can an O(n²) algorithm ever run faster than an O(n) algorithm?
Yes. Big-O notation hides constant factors and lower-order terms. For small values of n (such as n < 20), an algorithm with quadratic complexity T(n) = n² performs fewer total operations than a linear algorithm with high constant overhead T(n) = 100n. The linear algorithm only outperforms the quadratic algorithm once n exceeds the crossover point (n > 100).
What makes exponential O(2ⁿ) and factorial O(n!) problems so difficult?
Unlike polynomial algorithms where doubling the input increases work by a constant factor (4x for quadratic, 8x for cubic), exponential and factorial algorithms suffer from multiplicative compounding. Adding just one single element to an exponential problem doubles the entire workload; adding one element to a factorial problem multiplies the workload by n + 1. Beyond n ≈ 40, brute-force solutions cannot be solved within human lifespans on any earthly hardware.
How do time complexity and auxiliary space complexity differ?
Time complexity measures the total number of elementary operations executed as a function of input size n. Auxiliary space complexity measures the additional memory consumed by the algorithm beyond the input data itself. For example, Merge Sort achieves optimal O(n log n) time complexity but requires O(n) auxiliary space for buffer arrays, whereas Heap Sort achieves O(n log n) time complexity in O(1) in-place auxiliary space.
Does worst-case Big-O reflect average performance?
Not necessarily. Quick Sort has a worst-case time complexity of O(n²) if an unbalanced pivot is chosen, but its average-case time complexity is O(n log n) with extremely low constant factors. Similarly, hash table lookups take O(n) in the worst case if every key collides into a single bucket, but average O(1) with a uniform hash function. Rigorous algorithm analysis considers best, average, and worst cases independently.
How does input distribution affect runtime?
Some algorithms are adaptive, meaning their runtime improves when input data is partially sorted. In ToolSphere's Sorting Algorithm Visualizer, running Insertion Sort on an already-sorted array completes in O(n) time because every element is checked once without shifting. On reverse-sorted data, Insertion Sort drops to its worst-case O(n²) runtime because every element must shift across the entire sorted prefix.
Where can I test custom Big-O comparisons?
Open ToolSphere's interactive Big-O Complexity Calculator. You can input sizes from n = 1 to n = 1,000, assign distinct multipliers to models like O(n) versus O(n²), and observe the exact numerical operations alongside an interactive logarithmic scale chart.
See the growth rates in action with the sorting algorithm visualizer and the graph algorithm visualizer. For a side-by-side of real algorithms, read sorting algorithms compared.