Asymptotic Notations

Why a formal notation?

Earlier, O(n) and O($n^2$) were used informally, as labels for "roughly how T(n) scales." Asymptotic notation is what makes that informal label precise: a defined mathematical statement about how one function bounds another as n grows large, not just an intuition.

Three standard notations describe three different kinds of bound:

Big-O notation: O( )

In plain terms: from some point onward ($n \ge n_0$), f(n) never exceeds a constant multiple of g(n). g(n) is an upper bound, the algorithm never does asymptotically more work than this.

Once n crosses $n_0$, f(n) stays below the line $c \cdot g(n)$ for every n after that, no matter how f(n) wiggles before $n_0$.

Worked derivation: f(n) = 2n + 3

To show f(n) = O(n), find constants c and $n_0$ that satisfy the definition:

$2n + 3 \le c \cdot n \quad \text{for all } n \ge n_0$

Try c = 5:

$2n + 3 \le 5n \quad \text{for all } n \ge 1$

Checking n = 1: $2(1) + 3 = 5 \le 5(1) = 5$. True. And the gap only grows in g(n)'s favor as n increases. So c = 5 and $n_0 = 1$ work.

$g(n) = n, \quad \text{so } f(n) = O(n)$

Big-Omega notation: Ω( )

This is the mirror image of Big-O: g(n) is a lower bound, the algorithm never does asymptotically less work than this.

Once n crosses $n_0$, f(n) stays above the line $c \cdot g(n)$ for every n after that.

Worked derivation: f(n) = 2n + 3

$2n + 3 \ge c \cdot n \quad \text{for all } n \ge n_0$

Try c = 1:

$2n + 3 \ge 1 \cdot n \quad \text{for all } n \ge 1$

This holds for every $n \ge 1$, since $2n + 3$ is always at least n. So c = 1 and $n_0 = 1$ work.

$g(n) = n, \quad \text{so } f(n) = \Omega(n)$

Big-Theta notation: Θ( )

Θ requires both an upper and a lower bound with the same g(n), f(n) is sandwiched between $c_1 \cdot g(n)$ and $c_2 \cdot g(n)$. This is a tight bound: the function grows at exactly this rate, not just no-faster or no-slower.

Once n crosses $n_0$, f(n) stays trapped between the two lines $c_1 \cdot g(n)$ and $c_2 \cdot g(n)$ for every n after that.

Worked derivation: f(n) = 2n + 3

From the two derivations above: $1 \cdot n \le 2n + 3 \le 5 \cdot n$ for all $n \ge 1$.

$c_1 = 1, \quad c_2 = 5, \quad g(n) = n, \quad \text{so } f(n) = \Theta(n)$

Because O(n) and Ω(n) both held with the same g(n) = n, Θ(n) follows directly, Θ is what you get when the tightest upper bound and the tightest lower bound agree.

O vs Ω vs Θ

Notation	Meaning	Think of it as
O(g(n))	Upper bound	At most this order
Ω(g(n))	Lower bound	At least this order
Θ(g(n))	Tight bound	Exactly this order

Little-o and little-omega

O and Ω both allow f(n) to equal $c \cdot g(n)$ exactly, they are not strict. Two related notations tighten this to a strict inequality.

n belongs to $o(n^2)$, because n grows strictly slower than $n^2$. But n does not belong to o(n), since n is not strictly less than n, it is equal to it.

Worked derivation: is 2n = o(n²)?

To check, see whether $2n < c \cdot n^2$ holds for every positive c, no matter how small, once n is large enough.

$2n < c \cdot n^2 \quad \iff \quad \frac{2}{c} < n$

For any positive c, this holds once $n > 2/c$, so pick $n_0 = \lceil 2/c \rceil + 1$. Since this works for every choice of c, not just one, $2n = o(n^2)$: 2n grows strictly slower than $n^2$.

Contrast this with checking 2n = o(n): that would require $2n < c \cdot n$ for every c, i.e. $2 < c$ for every positive c, which fails the moment $c \le 2$. So 2n is not o(n), it is only O(n) and Θ(n), same-order growth is not strictly slower growth.

$n^2$ belongs to $\omega(n)$, because $n^2$ grows strictly faster than n. But n does not belong to $\omega(n)$, for the same reason as above, equality is not strict growth.

Worked derivation: is n² = ω(n)?

Check whether $n^2 > c \cdot n$ holds for every positive c, once n is large enough.

$n^2 > c \cdot n \quad \iff \quad n > c$

For any positive c, this holds once $n > c$, so pick $n_0 = \lceil c \rceil + 1$. This works for every c, so $n^2 = \omega(n)$.

But $n^2 = \omega(n^2)$ would require $n^2 > c \cdot n^2$ for every c, i.e. $1 > c$ for every positive c, which fails once $c \ge 1$. So $n^2$ is not $\omega(n^2)$, only $O(n^2)$, $\Omega(n^2)$, and $\Theta(n^2)$: a function is never strictly faster-growing than itself.

Notation	Meaning	Strictness
O(g(n))	Upper bound	Not strict (can be equal)
o(g(n))	Strict upper bound	Strict (must be strictly less)
Ω(g(n))	Lower bound	Not strict (can be equal)
ω(g(n))	Strict lower bound	Strict (must be strictly greater)
Θ(g(n))	Tight bound	Exact match

Why is there no "little-theta"?

Θ already means f(n) and g(n) grow at exactly the same rate, sandwiched between $c_1 \cdot g(n)$ and $c_2 \cdot g(n)$. o and ω exist to make O and Ω strict, ruling out the case where f(n) and g(n) happen to grow at the same rate. But Θ is built entirely around f(n) and g(n) growing at the same rate, that is the whole point of it, not a loophole to close. Making Θ "strict" in the o/ω sense would mean excluding the one case Θ exists to describe, which would leave nothing left to define. So there is nothing analogous to little-o and little-omega for Θ.

How to determine the notation for a T(n)

The dominant-term rule from "Ignore lower-order terms" (in the Time Complexity lesson) is exactly what tells you which g(n) to use here.

1. Identify the dominant term. For $T(n) = 3n^2 + 5n + 10$, the dominant term is $n^2$.
2. Apply the rule for the notation you want. All three notations use the same dominant term as g(n) for a typical polynomial:

$T(n) = 3n^2 + 5n + 10 \;\Rightarrow\; O(n^2), \; \Omega(n^2), \; \Theta(n^2)$

Note that this is only true because a single dominant polynomial term determines both the upper and lower bound at once. Not every function has this property, $100 + \log(n)$, for instance, is O(log n) and Ω(1) using the loosest correct bound, but its tightest correct classification is Θ(log n).

Quick recall

• Asymptotic notation makes "how T(n) scales" mathematically precise using constants c and $n_0$.
• Big-O: upper bound (at most this order). Big-Omega: lower bound (at least this order). Big-Theta: tight bound (exactly this order, both bounds agree).
• A function can satisfy multiple O or Ω bounds; always give the tightest one unless told otherwise. A function belongs to exactly one Θ.
• Little-o and little-omega are the strict versions of O and Ω, they exclude the case of equal growth.
• For a T(n) with multiple terms, identify the dominant term first, that term's order is usually the O, Ω, and Θ classification all at once.