---
title: 'Asymptotic Notation'
source: 'https://academia.sh/en/courses/algorithms/asymptotic-notation'
course: Algorithms
language: en
updated: '2026-08-17T18:07:31+00:00'
license: 'CC BY-SA 4.0'
---

# Asymptotic Notation

Definitions of big O, big omega, and big theta, elimination of constants, sum and product rules, and common misreadings.

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:

```python
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.