Concepts and theorems · Introductory

Big-O notation: bounding growth for large inputs

Define an asymptotic upper bound and distinguish it from a tight bound, a worst-case choice, and a wall-clock prediction.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. An eventual upper bound
  2. Bounding a simple function
  3. Worst-case is a separate choice
  4. Growth is not a complete benchmark
  5. Keep both input dimensions in the bound
  6. Ask Logeia about this articleCheck your understanding

An eventual upper bound

Big-O notation describes an eventual upper bound on a function, allowing a constant multiplier. Informally, T(n) is O(f(n)) if positive constants c and n0 can be chosen so that T(n)≤c·f(n) for every n≥n0. The inequality need not hold unchanged for all small inputs. This lets an analysis focus on growth with input size, but it does not claim that constants never matter in practice. State what resource T measures, such as comparisons, memory use, or another explicitly defined cost.

Bounding a simple function

For T(n)=3n+4, choosing c=7 works for n≥1, so the function is O(n). It is also O(n²), which is a valid but looser upper bound. Big-O does not mean exactly the same growth rate. A tight asymptotic bound is expressed with notation such as Theta when the corresponding lower bound also holds. Therefore, reading O(n²) as proof that a function necessarily grows quadratically is a mistake. Ask whether the author supplied only an upper bound or also established a matching lower bound.

Worst-case is a separate choice

Worst-case, expected, and amortized analyses select different quantities to bound. Big-O itself does not mean worst-case. Applying it to a worst-case cost function gives a worst-case upper bound; applying it to an expectation gives a bound on that expectation. Amortized analysis instead accounts for a sequence of operations. For example, an expected O(1) hash-table claim does not guarantee that every individual operation takes constant time on every input. The distributional or structural assumptions are part of the result and must travel with the notation.

Growth is not a complete benchmark

Two O(n) implementations can have different elapsed times because their constants, memory access patterns, parallelism, and setup costs differ. At a small input size, a simple quadratic implementation can even outperform an implementation with better asymptotic growth but substantial overhead. Asymptotic reasoning supplies a scaling perspective rather than replacing measurement. A useful comparison defines input size, identifies the resource being counted, and records the environment for any benchmark. Combine the mathematical model with representative measurements instead of treating a notation hierarchy as a universal ranking of real programs.

Keep both input dimensions in the bound

A traversal of an n-row, m-column table takes O(nm) element inspections when inspecting one element has constant cost. If m is always fixed at eight, the cost as a function of n is O(n). If m grows with n and m equals n, the same loop structure yields O(n²). Two nested loops therefore do not automatically establish a quadratic bound in one unspecified input size. If each iteration compares strings of length k, inspect whether treating that comparison as constant is justified. Define the input dimensions and primitive cost model before dropping variables or choosing a dominant term. This also makes a benchmark’s scaling assumptions easier to test.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 5

Prepare for AI systems · STEP 2

Choose a learning path