Asymptotic Notation

The previous lesson settled on operation count as the metric but left a problem: in a thousand-element array, whether 1000 or 1002 comparisons were made does not matter. These details depend on the implementation; what belongs to the algorithm itself is the rate at which the operation count grows as the input grows.

Asymptotic notation is the language that captures this rate and discards the rest.

Big O: Upper Bound

Let $f$ and $g$ be functions from positive integers to positive real numbers.

$$f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 \in \mathbb{N} : \forall n \geq n_0,\ f(n) \leq c \cdot g(n)$$

In words: if, for sufficiently large $n$, $f$ never exceeds a constant multiple of $g$, then $f$ grows at most as fast as $g$.

Both quantifiers in the definition are necessary. The constant $c$ eliminates factor-of differences — an implementation that runs twice as fast stays in the same class. The threshold $n_0$ eliminates irregularities at small inputs; an asymptotic statement is a claim about large inputs.

This can be shown explicitly with an example. For $f(n) = 3n^2 + 5n + 20$, choosing $g(n) = n^2$, the values $c = 4$ and $n_0 = 8$ satisfy the definition:

def f(n: int) -> int:
    return 3 * n**2 + 5 * n + 20

c, n0 = 4, 8
print(f(7) <= c * 7**2)            # False  — not satisfied below the threshold
print(f(8) <= c * 8**2)            # True
print(all(f(n) <= c * n**2 for n in range(n0, 10_000)))    # True

That it does not hold at seven is not a problem: the definition says something about what comes after the threshold. From eight onward, the inequality always holds; hence $3n^2 + 5n + 20 = O(n^2)$ is written.

Big Omega: Lower Bound

$$f(n) = \Omega(g(n)) \iff \exists\, c > 0,\ n_0 : \forall n \geq n_0,\ f(n) \geq c \cdot g(n)$$

Big O gives a ceiling, big omega gives a floor. It is used to say “this algorithm does at least this much work.”

Lower bounds are powerful when they are stated for a problem, not for a single algorithm: the statement “comparison-based sorting requires at least $\Omega(n \log n)$ comparisons” says that no comparison-based algorithm can go below this bound. This kind of result will be taken up together with the proof idea in the searching and sorting topic.

Big Theta: Tight Bound

$$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \ \text{ and } \ f(n) = \Omega(g(n))$$

Theta says that growth is exactly on the order of $g$: both the ceiling and the floor are the same function.

The expression $3n^2 + 5n + 20$ is $\Theta(n^2)$. The same expression is also $O(n^3)$ — an upper bound may be loose — but it is not $\Theta(n^3)$.

In everyday use, big O is often written while meaning a tight bound. This is a convenience; where precision matters, theta is preferred.

Simplification Rules

Complexity expressions simplify by a few rules.

Constant factors are eliminated. $O(3n) = O(n)$. The constant is already absorbed by the $c$ in the definition.

In a sum, the largest term remains. $O(n^2 + n) = O(n^2)$. Whichever of two sequential parts is more expensive is decisive.

In a product, factors are preserved. Costs multiply in nested loops: $O(n) \cdot O(\log n) = O(n \log n)$.

Transitivity holds. If $f = O(g)$ and $g = O(h)$, then $f = O(h)$.

Expression	Simplified	Reason
$5n + 100$	$O(n)$	Constants and the constant term are eliminated
$n^2 + 1000n$	$O(n^2)$	The larger term dominates
$\log_2 n$ and $\log_{10} n$	The same $O(\log n)$	A base change is a constant factor
$2^{n+1}$	$O(2^n)$	$2^{n+1} = 2 \cdot 2^n$
$n!$ and $2^n$	Different classes	Factorial grows faster than exponential

The third row answers a frequently asked point: a logarithm’s base is not specified, because a base change produces only a constant factor, and that factor is eliminated.

Finding the Constant and the Threshold

Proving a claim means producing a suitable $c$ and $n_0$. For polynomials there is a mechanical method: for $n \geq 1$, every lower-degree term is bounded by the dominant term, and the coefficients are summed.

In the example $f(n) = 3n^2 + 5n + 20$, for $n \geq 1$ it can be written that $5n \leq 5n^2$ and $20 \leq 20n^2$. Summed, this gives $f(n) \leq 28n^2$; that is, $c = 28$, $n_0 = 1$ is also a valid pair that satisfies the definition.

Above, a smaller constant was found with $c = 4$, but it was not necessary: the definition asks for the existence of a pair, not the smallest one. This explains why asymptotic claims are easy to prove — even a crude bound suffices.

Common Misreadings

“$O(n)$ does not mean exactly $n$ operations.” It is an upper bound; $3n$ and $n/2$ are both $O(n)$.

“$O$ does not mean worst case.” These are two separate axes. $O$, $\Omega$, and $\Theta$ can each be written separately for the best, worst, and average case. “$O(n^2)$ in the worst case” and “$O(n^2)$ in every case” are different claims.

“A smaller class is not always better.” Because asymptotic notation eliminates constants, an $O(n \log n)$ algorithm can be slower than an $O(n^2)$ algorithm on small inputs. This is why sorting libraries apply a different algorithm to small chunks.

The notation is not an equality. The way of writing $f(n) = O(g(n))$ is established but misleading; correctly, it is set membership of the form $f \in O(g)$. For this reason the equality is not symmetric: $O(n) = f(n)$ is not written.

What Is Input Size

One last definition is needed: what does $n$ count? The answer varies by problem, and the expression is meaningless if it is not specified.

• In array operations, the number of elements.
• In text algorithms, the number of characters.
• In graph algorithms, both the number of nodes and the number of edges — this is why costs are written with two variables, as in $O(V + E)$.
• In numerical algorithms, usually the number’s bit length; not the number itself.

The last item is a subtle distinction. A method that tests whether a number is prime by dividing up to the number itself appears to be $O(\sqrt{N})$ if the number’s value is taken as the input; but the input is not $N$, it is the number of bits needed to write it. In terms of bit length, the same method is exponential. This distinction is the foundation of classification in complexity theory and is taken up in the Theory of Computation course.

Summary

• Asymptotic notation eliminates constants and lower-order terms, keeping only the growth rate.
• Big O gives an upper bound, big omega a lower bound, big theta a tight bound.
• The constant $c$ in the definition eliminates factor-of differences, and the threshold $n_0$ eliminates small inputs.
• In simplification, constants are eliminated, the largest term remains in a sum, and factors are preserved in a product; a logarithm’s base is not written, because a base change is a constant factor.
• $O$ and “worst case” are different axes; a smaller asymptotic class does not guarantee being fast on small inputs.
• What is counted as input size must be stated explicitly.

Next Step

Big O and omega do not say whether a bound is tight: $n$ is both $O(n)$ and $O(n^2)$. The next lesson will define the little notations that state a bound is strictly loose, and show what statements they make possible.