Big O notation describes how an algorithm’s cost grows with its input, discarding machine-specific constants so competing approaches can be compared by growth rather than one benchmark on one machine.
Formally, f(n) = O(g(n)) means f grows no faster than g beyond some input size. Constants c and n₀ exist such that f(n) ≤ c · g(n) for all n ≥ n₀. Constant factors disappear (3n + 100 is O(n)), as do lower-order terms (n² + n is O(n²)), because the fastest-growing term dominates as n → ∞. This makes scaling comparable across machines. Big O alone still cannot rank algorithms within the same class or distinguish a tight bound from a loose upper bound, and at n = 20 the discarded constants may dominate.
The same notation measures time and space. Time complexity counts operations as a function of input size. Space complexity counts extra memory, including recursion frames that can overflow the call stack.
Core idea: cost as a function of n, keep only the dominant term, drop constants → a hardware-independent growth class that predicts behaviour at scale but not at small n.
The growth classes, side by side
The complexity class is the shape of the curve. Every line begins at the visual origin, then the logarithmic vertical scale covers 1 to 10k operations over the bounded n = 2…10 domain. Factorial is evaluated only through 10!. Once a curve exceeds 10k it leaves the plot, which makes the exponential and factorial jumps visible instead of compressing every practical class against the baseline.
Growth of common complexity classes
Complexity catalogue
Complexity
Growth
Typical example
O(1)
Same time regardless of input size
Array indexing or a well-distributed hash lookup
O(log log n)
Shrinks faster than a fixed-factor split under a strong distribution assumption
At n = 10, n² is 100, 2ⁿ is 1,024, and n! is 3,628,800. Polynomial versus exponential growth is the conventional theoretical tractability boundary, not a guarantee of practical feasibility: an O(2ⁿ)brute-force search usually becomes impractical in the dozens and an O(n!) permutation search in the low teens. The exact cutoff depends on the hardware, latency budget, and work done per state.
The chart’s crossover understates the gap at real input sizes. Counting operations at a few scales makes it concrete:
n
log₂ n
n
n log₂ n
n²
2ⁿ
10
~3
10
~33
100
~1,000
100
~7
100
~664
10,000
~1.3 × 10³⁰
1,000
~10
1,000
~10⁴
10⁶
~10³⁰¹
1,000,000
~20
10⁶
~2 × 10⁷
10¹²
beyond astronomical
At a million elements, log₂ n is still about 20 while n² is a trillion. No constant-factor tuning rescues an n² algorithm at that scale. Changing it to n log n cuts the operation count by roughly 50,000 times. The 2ⁿ column passes 10³⁰ at n = 100, so an exponential bound is usually a signal to look for dynamic programming, a greedy rule, or an approximation instead of a larger machine.
Common DSA pattern complexities
The table uses n for processed elements, k for a retained subset or window size, m for the number of disjoint-set operations, R for the number of candidate answer values, and C for the cost of one feasibility check. α(n) is the inverse Ackermann function, which grows so slowly that it is effectively constant at practical sizes.
Each element is pushed once and popped at most once, so individual pops amortize across the scan.
Common data-structure operations
V and E denote graph vertices and edges, deg(v) is the degree of vertex v, and L is key length for a trie. Average hash-table bounds assume a suitable hash function and controlled load factor. Amortized bounds describe a sequence of operations, not the worst cost of one call.
Structure
Access / lookup
Insert
Remove
Explanation
Static array
Index O(1). Value search O(n)
At position O(n)
At position O(n)
Contiguous indexing is constant. Interior edits shift a suffix.
Make-set O(1). Union update/merge O(α(n)) amortized
Unsupported
The inverse-Ackermann bound requires path compression and union by rank/size. A standard disjoint-set forest cannot split a set by removing an element.
Graph adjacency list
Edge lookup O(deg(u)). Neighbor scan O(deg(u))
Edge O(1) amortized
Edge O(deg(u))
Space is O(V + E). Using a set per neighbor list changes expected edge lookup/update toward O(1) at extra overhead.
Graph adjacency matrix
Edge lookup O(1). Neighbor scan O(V)
Edge O(1)
Edge O(1)
Space is O(V²), which pays for constant-time edge membership.
Space complexity and the cases
Space includes the call stack. A recursive traversal that allocates O(1) heap memory may still use O(h) stack frames, where h is the recursion depth. A chain-shaped input 100k nodes deep can overflow a thread stack without allocating heap objects. Auxiliary space means memory beyond the input: merge sort uses O(n) for its merge buffer, naive recursive quicksort uses O(log n) expected and O(n) worst-case stack space, while an in-place scan uses O(1).
A single algorithm has different bounds depending on the input, and the distinction is not pedantic:
Worst case — the guarantee under adversarial or degenerate input. What an SLA or a security boundary is written against. A hash-map lookup is O(n) worst case when every key collides.
Average case — expected cost over a distribution of inputs. A hash-map lookup is O(1) average, a bound commonly used for capacity planning.
Best case — the floor. Usually uninteresting except to note it (a target found on the first probe is O(1)).
Amortised — cost averaged over a sequence of operations, distinct from average case. Dynamic-array append is O(1) amortised even though a single resize is O(n), and union-find is O(α(n)) amortised per operation — a guarantee over the whole sequence, not any one call.
Big O states an upper bound. Big Θ (theta) states a tight bound where the upper and lower bounds match: merge sort is Θ(n log n) in every case, while quicksort is O(n²) worst case and Θ(n log n) on average. Big Ω (omega) states a lower bound. Informal discussion often uses “O” for a tight bound, but Θ is the precise notation for matching asymptotic upper and lower bounds.
Reading complexity off the code (C#)
// O(n): one pass, work per element is O(1).long Sum(int[] a){ long total = 0; foreach (var x in a) total += x; // n iterations × O(1) return total;}// O(n²): a loop inside a loop, each O(n).bool HasDuplicate(int[] a){ for (var i = 0; i < a.Length; i++) for (var j = i + 1; j < a.Length; j++) // ~n²/2 pairs → drop the ½ → O(n²) if (a[i] == a[j]) return true; return false;}// O(n): the same question, one pass, trading O(n) space for the second loop.bool HasDuplicateFast(int[] a){ var seen = new HashSet<int>(); // O(n) auxiliary space foreach (var x in a) if (!seen.Add(x)) return true; // O(1) average per element → O(n) total return false;}
HasDuplicate and HasDuplicateFast answer the same question. The second trades O(n) memory to drop time from O(n²) to O(n). Reading a bound is mostly counting nested loops and multiplying by the per-iteration cost, then discarding constants and lower-order terms.
Where Big O misleads
Constants matter at small n. Big O drops them, so an O(n log n) algorithm with heavy setup can lose to an O(n²) one on small inputs. Array.Sort switches to insertion sort for small subarrays inside its O(n log n) introsort because the quadratic algorithm has a smaller constant on short partitions.
The hidden constant can be huge. Two O(n) algorithms can differ 100× in wall-clock from cache behaviour, branch prediction, or allocation. Big O narrows the field. Profiling on representative data picks the winner within a class.
“n” must be defined. For string work, is n the number of strings or their total length? A trie lookup is O(L) in key length, independent of the n keys stored — stating the bound without naming the variable is meaningless.
The base of a logarithm is irrelevant.log₂ n and log₁₀ n differ by a constant factor, which Big O drops, so O(log n) needs no base. Inside an exponent the base is decisive: 2ⁿ and 3ⁿ are different classes.
Questions
What does Big O notation describe?
Big O notation describes an upper bound on how an algorithm’s cost, usually running time or extra memory, grows as a function of input size n. It states how an approach scales, not how long it takes on a particular machine.
Formally, f(n) = O(g(n)) means positive constants c and n₀ exist such that f(n) ≤ c · g(n) for every n ≥ n₀. Beyond some input size, the cost grows no faster than a fixed multiple of g(n).
Upper bound, not necessarily tight: a loose bound is still true, so a linear-time algorithm is also O(n²). A bound that holds from both above and below is tight and is written Θ.
Defined input size: a bound is meaningful only once n is stated. For string processing, n can count strings or total characters, and the two can give different bounds.
Why does Big O notation drop constant factors and lower-order terms?
They cannot change an expression’s growth class, so dropping them loses nothing that Big O expresses. Its definition only requires some fixed constant c and starting size n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀. A constant factor can be folded into c. A lower-order term grows more slowly than the dominant term. Beyond some size, it is therefore at most a fixed multiple of that term and can be folded into c as well.
For example, when n ≥ 1, each term of n² + 100n + 500 is at most a multiple of n²:
n² + 100n + 500 ≤ n² + 100n² + 500n² = 601n²
So c = 601 and n₀ = 1 satisfy the definition, and the expression is O(n²), the same class as n² or 5n².
The class describes eventual growth only. The discarded parts still affect actual cost: for every n up to 104, 100n + 500 is larger than n² itself.
What is the difference between average-case and amortized complexity?
Average-case complexity is the expected cost when inputs or random choices follow a stated probability distribution. Amortized complexity is a guaranteed bound on the total cost of a sequence of operations, spread across those operations. Amortized analysis uses no probability, so it is not a kind of average-case analysis.
Aspect
Average case
Amortized
What is averaged
The cost of an operation over possible inputs or random choices, weighted by their probability.
The total cost of a sequence of operations, divided by the number of operations.
Assumption
A stated distribution. If real inputs do not follow it, the bound does not describe them.
No distribution. The bound holds for every sequence the analysis covers.
What can still be slow
A particular unlucky or adversarial input can cost much more than expected.
A single operation can be expensive, but expensive steps are rare enough that the sequence total stays within the bound.
Example
A hash lookup is constant time on average only under suitable hashing and collision assumptions.
Dynamic-array append is amortized O(1). A resize copies every element in O(n), but growing capacity by a constant factor, such as doubling, keeps the total for n appends at O(n).