Asymptotic Analysis: Big-O and What It Hides

Asymptotic analysis is a language for comparing cost functions as input size grows. It is not a stopwatch, a synonym for worst case, or a rule that says “delete constants.” A statement such as $T(n)\in O(n\log n)$ becomes meaningful only after defining the inputs, the size measure $n$, the resource being counted, the computational model, and the case or probability distribution.

Khan Academy's explainer gives a useful first intuition: Big-O is an eventual upper bound, whereas Big-Theta is a tight order. Wikipedia's broad survey is useful for navigating the notation's mathematical and computer-science variants. This chapter builds the durable account from primary and official sources, then makes the assumptions that short explainers usually leave implicit.

Start with a cost contract #

An analysis needs six named choices:

1. Input family: which objects are valid inputs?
2. Size measure: what number or tuple describes input size?
3. Resource: time, comparisons, allocations, bytes, I/O transfers, messages, or something else?
4. Primitive operation: what costs one unit in the chosen model?
5. Case: worst, best, distributional average, randomized expectation, or amortized sequence?
6. Output convention: is producing the output itself included?

flowchart LR
    X["Concrete input x"] --> S["Size measure |x| = n"]
    X --> C["Cost C(x) in a named model"]
    S --> K["Case or distribution"]
    C --> K
    K --> T["Cost function T(n)"]
    T --> A["Asymptotic class O, Ω, Θ, o, or ω"]

For deterministic algorithm $A$, let $C_A(x)$ be the counted cost on input $x$. If $X_n$ is the set of valid inputs of size $n$, assume here that each $X_n$ is nonempty and finite, as it is for ordinary finite encodings. Otherwise the extrema below may need $\sup$ and $\inf$ in place of an attained maximum and minimum. Several different functions can then be derived from the same code:

$$T_{\mathrm{worst}}(n)=\max_{x\in X_n} C_A(x),$$

$$T_{\mathrm{best}}(n)=\min_{x\in X_n} C_A(x),$$

and, after choosing a probability distribution $\mu_n$ over $X_n$,

$$T_{\mathrm{avg},\mu}(n)=\mathbb E_{x\sim\mu_n}[C_A(x)].$$

These are different mathematical objects. Each may separately have an upper, lower, or tight asymptotic bound.

For a randomized algorithm with random bits $R$, another common function is

$$T_{\mathrm{rand}}(x)=\mathbb E_R[C_A(x,R)],$$

where $x$ is fixed and the expectation is over the algorithm's choices. A worst-input expected bound then studies $\max_{x\in X_n}T_{\mathrm{rand}}(x)$. This is not the same as averaging over a friendly input distribution.

The size measure is part of the theorem #

“Linear time” means linear in a declared size. A positive integer with numerical value $N\ge 1$ occupies

$$b=\lfloor\log_2 N\rfloor+1$$

bits in ordinary binary encoding. A loop that executes $N$ times is $\Theta(N)$ in the numeric value but $\Theta(2^b)$ in the bit length. Calling it simply “linear” hides the representation that determines the actual input size.

A graph likewise has at least two natural parameters, $V$ vertices and $E$ edges. An adjacency-list representation occupies $\Theta(V+E)$ entries, while an adjacency matrix occupies $\Theta(V^2)$ entries. A traversal described only as “linear” has not yet said linear in which representation.

From code to a cost function #

Do not guess the asymptotic class from indentation. Count how often the chosen primitive operation executes.

A linear loop #

for i = 0 to n - 1:
    inspect(a[i])

If inspect, loop comparison, increment, and indexing are constant-cost Word-RAM operations, the exact cost has the form

$$T(n)=an+b$$

for model-dependent constants $a>0$ and $b$. Therefore $T(n)\in\Theta(n)$. The exact constants matter for measurement; the asymptotic classification deliberately forgets them.

A triangular loop #

for i = 1 to n:
    for j = 1 to i:
        work()

The inner operation runs

$$1+2+\cdots+n=\frac{n(n+1)}2$$

times, so the work is $\Theta(n^2)$. “Two loops means quadratic” happens to work here, but the sum—not the nesting—is the proof.

A geometrically shrinking loop #

while n > 1:
    n = floor(n / 2)

For an integer starting value $n\ge 1$, after $k$ iterations the value is $\lfloor n/2^k\rfloor$. The first time this value is at most $1$ occurs after

$$k=\lfloor\log_2 n\rfloor$$

iterations. For example, $n=3$ becomes $1$ in one step. The exact floor depends on the loop guard and rounding rule; the iteration count is $\Theta(\log n)$ either way.

Nested loops need not produce linearithmic work #

i = 1
while i < n:
    repeat i times:
        work()
    i = 2 * i

The blocks cost $1,2,4,\ldots,2^k$ with $2^k<n\le2^{k+1}$. Their sum is below $2^{k+1}<2n$, while the last completed block is at least a constant fraction of $n$. Total work is therefore $\Theta(n)$, not $\Theta(n\log n)$.

A library call is not automatically constant #

map[key], string comparison, integer multiplication, allocation, and sorting all hide algorithms. An analysis may treat one as primitive only because the computational model grants that cost or because a separate bound has been substituted.

For example, binary search performs $O(\log n)$ key comparisons. If comparing two keys can inspect $L$ characters, its time is $O(L\log n)$, not necessarily $O(\log n)$. The comparison count and the running-time bound answer different questions.

The computational model sets the unit price #

A Word-RAM model stores $w$-bit words and assigns unit cost to an explicitly declared instruction set acting on $O(1)$ words. To address $n$ memory words, a word must hold an address, so its width satisfies $w=\Omega(\log n)$ bits. The MIT 6.006 course variant used here grants constant cost to its listed word arithmetic, comparisons, bit operations, and random-access reads and writes. Other Word-RAM variants expose different primitive operations, so a proof must name the instruction set it assumes.

This does not make arbitrary-precision arithmetic constant. If an integer occupies $b$ bits, merely reading all of it costs $\Omega(b/w)$ word operations. Its addition and multiplication costs must be analyzed as functions of $b$ under the chosen integer algorithm. A unit-cost model with unlimited-width integers would smuggle an unrealistic amount of work into one step.

Other models price other events:

Big-O does not force the RAM model. It can classify any well-defined resource function. “Big-O ignores I/O” is therefore wrong: ordinary analyses often choose not to count I/O, while external-memory analysis explicitly counts block transfers.

The five core asymptotic relations #

For algorithm analysis, let $f,g:\mathbb N\to\mathbb R_{\ge0}$ and assume $g(n)>0$ for all sufficiently large $n$. The definitions concern what happens eventually.

Big-O: eventual upper bound #

$$f\in O(g) \iff \exists c>0\;\exists n_0\;\forall n\ge n_0: 0\le f(n)\le c\,g(n).$$

One fixed multiplier $c$ must work for every $n$ after one fixed threshold $n_0$.

Big-Omega: eventual lower bound #

$$f\in\Omega(g) \iff \exists c>0\;\exists n_0\;\forall n\ge n_0: 0\le c\,g(n)\le f(n).$$

In computer science this is Knuth's lower-bound convention. Analytic number theory also uses an older Hardy-Littlewood $\Omega$ with different semantics, so the field and definition matter.

Big-Theta: tight order up to constants #

$$f\in\Theta(g) \iff \exists c_1,c_2>0\;\exists n_0\;\forall n\ge n_0: 0\le c_1g(n)\le f(n)\le c_2g(n).$$

Equivalently,

$$f\in\Theta(g)\iff f\in O(g)\cap\Omega(g).$$

$\Theta(g)$ says that $f/g$ stays between two positive constants eventually. It does not say that $f/g\to1$. The stronger relation $f\sim g$ is asymptotic equivalence and belongs to limits and asymptotics.

Little-o: strictly smaller order #

$$f\in o(g) \iff \forall c>0\;\exists n_0\;\forall n\ge n_0: 0\le f(n)<c\,g(n).$$

The threshold may depend on $c$. For eventually positive $g$, this is equivalent to $f(n)/g(n)\to0$.

Little-omega: strictly larger order #

$$f\in\omega(g) \iff \forall c>0\;\exists n_0\;\forall n\ge n_0: 0\le c\,g(n)<f(n).$$

Equivalently, $g\in o(f)$ under the same positivity assumptions.

The common notation $f(n)=O(g(n))$ is conventional but not an ordinary symmetric equality. It means membership in a class of functions. Writing $f\in O(g)$ makes the direction explicit:

$$n\in O(n^2), \qquad n^2\notin O(n).$$

Reversing the first statement changes its truth value.

Proofs need witnesses, not crossed-out terms #

“Drop constants and lower-order terms” is a useful consequence of the definitions for familiar nonnegative costs. It is not a definition and is not a proof.

Prove a tight polynomial bound #

Let

$$f(n)=3n^2+7n+4.$$

For $n\ge1$, both $n\le n^2$ and $1\le n^2$, so

$$3n^2 \le 3n^2+7n+4 \le 3n^2+7n^2+4n^2 =14n^2.$$

The witnesses $c_1=3$, $c_2=14$, and $n_0=1$ prove

$$3n^2+7n+4\in\Theta(n^2).$$

Many other valid witnesses exist. The definition asks for existence, not the smallest constants or threshold.

Disprove an alleged upper bound #

Suppose $n^2\in O(n)$. Then some fixed $c,n_0$ would satisfy $n^2\le cn$ for every $n\ge n_0$, hence $n\le c$. Choosing $n>\max\{c,n_0\}$ contradicts that inequality. Therefore

$$n^2\notin O(n).$$

To disprove Big-O, show that every proposed constant and threshold eventually fail.

Prove a strict bound #

To show $n^2\in o(n^3)$, start with an arbitrary $c>0$. The required inequality is

$$n^2<c n^3,$$

which holds whenever $n>1/c$. Choosing $n_0=\lfloor1/c\rfloor+1$ proves the statement. The dependence of $n_0$ on the arbitrarily chosen $c$ is exactly what distinguishes little-o from Big-O.

Logarithm bases differ by a constant #

For fixed bases $a,b>1$,

$$\log_a n=\frac{\log_b n}{\log_b a}.$$

The factor $1/\log_b a$ is constant, so all fixed-base logarithms lie in $\Theta(\log n)$. This does not apply when the base varies with $n$, and it does not make different exponential bases equivalent:

$$2^n\in O(3^n), \qquad 3^n\notin O(2^n).$$

Big-O can be true and still uninformative #

Because $n\le n^2$ for $n\ge1$,

$$n\in O(n^2).$$

The bound is valid but loose. A tight statement is $n\in\Theta(n)$. When someone asks for “the Big-O of an algorithm,” they normally want the tightest simple upper bound that the analysis establishes, even though the notation itself permits looser answers.

Not every pair of functions is comparable #

Define

$$f(n)= \begin{cases} n^2,&n\text{ even},\\ n,&n\text{ odd}, \end{cases} \qquad g(n)= \begin{cases} n,&n\text{ even},\\ n^2,&n\text{ odd}. \end{cases}$$

On even inputs $f/g=n$, which is unbounded; on odd inputs $g/f=n$, which is unbounded. Thus neither $f\in O(g)$ nor $g\in O(f)$. Big-O induces an asymptotic preorder, not a total ranking of all functions.

Algebra that is safe—and traps that are not #

For eventually nonnegative functions, the following rules justify most everyday simplifications.

These rules have conditions.

• Cancellation can change the order. The expression $n^2-n^2+n$ is exactly $n$, not $\Theta(n^2)$. Analyze the simplified value, not isolated terms with signs ignored.
• Subtraction is not monotone. From $f\le cg$ and $h\le ck$, no useful bound on $f-h$ follows without more information.
• Composition needs monotonicity and domain control. From $n\in O(n^2)$, applying the decreasing function $F(x)=1/x$ does not yield $1/n\in O(1/n^2)$.
• A hidden constant cannot depend on a growing input parameter. If $T(n,k)=kn$, then for every fixed $k$, $T(\cdot,k)\in O(n)$. It is not uniformly $O(n)$ when $k$ grows without bound.
• Loop multiplication needs independence of ranges. A nested loop whose total inner ranges form a geometric or telescoping sum may be linear.

The common growth hierarchy #

For fixed constants $0<\varepsilon<1$, $k>1$, and $c>1$, familiar eventually positive functions satisfy

$$1 \prec \log\log n \prec \log n \prec n^\varepsilon \prec n \prec n\log n \prec n^k \prec c^n \prec n!,$$

where $f\prec g$ here means $f\in o(g)$.

The hierarchy compares eventual growth, not running time at one input size. It also says nothing about whether two algorithms compute the same result correctly.

Constants and crossover points still govern finite inputs #

Compare two exact model costs:

$$T_A(n)=1000n, \qquad T_B(n)=n^2.$$

$T_A\in\Theta(n)$ and $T_B\in\Theta(n^2)$, so $A$ has the better asymptotic order. For positive input sizes, $B$ uses fewer operations whenever $0<n<1000$. The costs also meet at the trivial origin; the meaningful positive crossover is $n=1000$, after which the linear algorithm wins.

The example does not show that constants are “more important” than growth rates. It shows that an engineering decision needs both:

1. an asymptotic model to understand scaling outside the measured range;
2. constants and measurements to choose within the real range of inputs and hardware.

The threshold $n_0$ in a Big-O proof is existential. Big-O alone does not report it. Nor does it report the witness constant $c$.

Worst, best, average, expected, and amortized are separate axes #

The notation and the case describe different aspects of a cost function.

Then $O$, $\Omega$, or $\Theta$ may be applied to any row.

Binary search shows the distinction #

For successful binary search on a sorted array:

• the best-case comparison count is $\Theta(1)$ when the first midpoint matches;
• the worst-case comparison count is $\Theta(\log n)$;
• either function separately has many true loose upper bounds.

Saying only “binary search is $O(\log n)$” conventionally communicates a worst-case upper bound, but the word worst comes from the chosen cost function, not from the letter $O$.

Average case needs a distribution #

There is no mathematical “average input” without weights. Uniform over input values, uniform over permutations, a product distribution over bits, and an empirical production distribution can give different expectations. State $\mu_n$ and whether it changes with $n$.

Randomized expectation fixes the ordinary input #

On $n$ distinct keys, randomized quicksort has expected $O(n\log n)$ comparisons for every fixed input ordering when pivots are chosen independently and uniformly. The expectation is over the pivot choices. This guarantee is stronger than saying that deterministic quicksort is fast on a random permutation.

Amortized is not probabilistic #

In a doubling dynamic array, one append can cost $\Theta(n)$ because it copies the existing elements. Across a sequence that grows the array from empty, copy costs form

$$1+2+4+\cdots <2n.$$

The total cost of $n$ appends is $\Theta(n)$, so the amortized cost is $\Theta(1)$ per append. This is a deterministic bound over allowed sequences, not an expectation over random operations. Aggregate, accounting, and potential proofs belong in amortized analysis.

Multiple input parameters require uniform bounds #

Suppose $T(n,k)=kn$. Two different statements are possible:

1. for each fixed $k$, $T(n,k)\in O(n)$ as $n\to\infty$;
2. uniformly over growing $n$ and $k$, $T(n,k)\in\Theta(nk)$.

The first allows a hidden constant that depends on fixed $k$; the second does not. Writing merely $O(n)$ while both inputs grow is false.

For a function $T(n,m)$, define the domain and limiting process. A statement such as

$$T(n,m)\in O(nm)$$

normally means that fixed $c,n_0,m_0$ exist such that $T(n,m)\le cnm$ for every $n\ge n_0$ and $m\ge m_0$ in the declared domain. If the domain imposes $m\le n$, that relationship is also part of the theorem.

Graph bounds should preserve vertices and edges #

For single-source breadth-first search, let $V_r$ be the vertices reachable from the source and let $E_r$ count the stored outgoing-edge entries examined from them. After any $\Theta(V)$ initialization of per-vertex state, an adjacency-list search does $\Theta(V_r+E_r)$ traversal work; a BFS forest that restarts from every unvisited vertex gives the familiar $\Theta(V+E)$ total. With an adjacency matrix, single-source search scans a row of $V$ entries for every reached vertex, giving $\Theta(VV_r)$ traversal work, while a full forest gives $\Theta(V^2)$. The representation and traversal scope both change the cost function.

Output-sensitive bounds name the answer size #

If an algorithm must emit $K$ distinct records, it needs $\Omega(K)$ output operations in an ordinary sequential-output model. A bound such as

$$O(n\log n+K)$$

separates preprocessing from unavoidable output work. Hiding $K$ behind $n$ can make an impossible promise: no algorithm can explicitly print exponentially many answers in polynomial time measured only in $n$.

Preprocessing changes the workload equation #

Suppose a static unsorted array of $n$ keys receives $q$ membership queries. Work in the comparison model, use a comparison sort with worst-case $\Theta(n\log n)$ comparisons, and compare worst-case total comparisons across the whole query sequence.

• Scan for every query: $\Theta(qn)$ total comparisons in the worst case, attained when every query misses or matches only at the end.
• Sort once and binary-search: $\Theta(n\log n+q\log n)$ worst-case total comparisons.

One query does not justify sorting: $\Theta(n)$ beats $\Theta(n\log n)$. For many queries, the preprocessing can pay back. The rough crossover solves

$$qn>n\log n+q\log n,$$

so, when $n\gg\log n$, sorting becomes asymptotically attractive around $q=\Theta(\log n)$ queries. Exact constants, update frequency, key-comparison cost, memory, and cache locality determine the practical threshold.

This is why a complexity claim should cover the whole workload lifecycle rather than quote one operation in isolation.

Time and space are different functions #

Space analysis should state what it counts.

• Total space includes the input representation, output, and working memory.
• Auxiliary space excludes the input and often excludes required output, counting only extra workspace.
• Peak live space counts memory simultaneously reachable at the maximum point, not cumulative bytes ever allocated.
• Stack space includes active recursion frames unless the implementation contract proves tail-call elimination or uses an explicit stack.

An in-place algorithm may use $O(1)$ auxiliary words while still occupying $\Theta(n)$ total space for its input. An algorithm that streams $K$ output records may use $O(1)$ auxiliary space even though it emits $\Theta(K)$ bytes over time; one that materializes them uses $\Theta(K)$ additional peak space.

Time-space tradeoffs should therefore be written as a pair, such as

$$T(n)\in\Theta(n\log n), \qquad S_{\mathrm{aux}}(n)\in\Theta(n).$$

What asymptotic notation intentionally hides #

A valid asymptotic result does not determine all performance-relevant behavior.

The right response is not to abandon asymptotic analysis. It is to add the model needed by the decision:

• use the external-memory model for block transfers;
• use work and span for parallelism;
• use bit complexity for growing integers;
• use cache analysis or hardware counters for locality;
• benchmark representative ranges after the analytic model is sound.

Complexity of an algorithm is not complexity of a problem #

Analyzing one algorithm proves a bound for that algorithm under a model. It does not automatically prove that every algorithm must pay the same cost.

• An algorithmic upper bound constructs a procedure using at most a stated resource.
• A problem lower bound proves that every algorithm in a specified model needs at least a stated resource on some inputs.
• A tight problem bound matches upper and lower bounds under the same model.
• A complexity class groups decision problems by resource-bounded machine definitions and reductions.

For example, a quadratic sorting implementation does not prove that sorting requires quadratic time. In the comparison model, a decision-tree lower bound and an $O(n\log n)$ comparison sort together establish $\Theta(n\log n)$ comparison complexity. The machinery of reductions, P, NP, and completeness belongs in complexity classes.

A repeatable analysis workflow #

1. State the contract. What must the algorithm compute, and what counts as success?
2. Name the input family and size. Use a tuple when one number destroys meaningful structure.
3. Choose the resource and model. Comparisons, word operations, bits, bytes, transfers, messages, work, or span?
4. Define the case. Worst, best, named input distribution, algorithmic randomness, or amortized sequence?
5. Expose hidden subcosts. Replace library operations with their contracts and parameter-dependent costs.
6. Derive a cost expression. Use sums, recurrences, charging, or probability—not visual guesses from code shape.
7. Prove the asymptotic claim. Supply witnesses, an invariant, a limit under valid conditions, or a reduction to known bounds.
8. Check tightness. Is the result only an upper bound? Can a matching lower bound be shown?
9. Audit omitted dimensions. Space, output, integer width, preprocessing, I/O, cache, parallelism, and tails.
10. Measure the real regime. Validate constants, crossover points, and model assumptions on representative data.

Compact diagnostic checklist #

Before accepting a complexity statement, ask:

• What exactly is $n$?
• Is the bound uniform over every other growing parameter?
• Which cost function receives the $O$, $\Omega$, or $\Theta$ label?
• Are constants independent of input size?
• Does the primitive-operation model match the data representation?
• Is output size included?
• Are expected and average-case claims tied to explicit probability spaces?
• Is amortized analysis being confused with average case?
• Is a loose upper bound presented as though it were tight?
• Does the claim survive large keys, sparse graphs, recursion depth, and preprocessing costs?
• Does a different model—bits, blocks, cache misses, or span—control the actual decision?
• Has correctness been proved separately?

Worked diagnosis: four common mistakes #

“Two nested loops are always quadratic” #

False. Write the total as a sum. Independent ranges of length $n$ give $n^2$ iterations; triangular ranges give $n(n+1)/2$; geometric block lengths can sum to $\Theta(n)$.

“Hash lookup is O(1)” #

Incomplete. State whether this is expected, amortized, or worst-case; identify the hashing assumptions; include key length and resize cost; and distinguish operation count from cache behavior. The full contract belongs in hash tables.

“The algorithm is polynomial because it is O(n^k)” #

Only if $k$ is a fixed constant independent of the input. A running time $n^k$ with $k$ supplied as part of the input is not bounded by one fixed polynomial in the combined input size.

“The faster asymptotic class wins” #

Only eventually under the analyzed model. The finite crossover can lie beyond available memory, latency budgets, or all realistic inputs. Compare exact costs or measurements in the operating range while retaining the asymptotic scaling argument.

Final mental model #

An asymptotic class is an eventual envelope around a cost function. The cost function comes from a prior modeling decision:

$$\text{algorithm} +\text{input encoding} +\text{resource model} +\text{case} \longrightarrow T(n) \longrightarrow \text{asymptotic relation}.$$

If any term on the left is missing, the complexity label is ambiguous. If all are explicit, Big-O and its relatives become rigorous, composable tools: they prove scaling, expose representation choices, compare strategies beyond one machine, and tell you exactly which practical questions still require another model or a measurement.