6 · Asymptotic notation: O, Ω, Θ

In one sentence

$O$ , $\Omega$ and $\Theta$ compare how fast functions grow for large $n$ , ignoring constant factors and small inputs. $O$ is "at most", $\Omega$ is "at least", and $\Theta$ is "exactly, up to constants".

Everyday analogy

Speed limits on a motorway. " $f = O(g)$ " is like "this car never goes faster than $c\times$ the speed limit $g$ , once it's on the motorway (after $n_0$ )". " $\Omega$ " is a minimum speed. " $\Theta$ " means the car stays between a minimum and a maximum, so it is "in the same lane" as $g$ . What happens in the car park before the motorway (small $n$ ) doesn't count.

Definitions

Notation	Means	Formal definition: there exist positive constants…
$f(n) = O(g(n))$	$f$ grows no faster than $g$	$c, n_0$ with $0 \le f(n) \le c\,g(n)$ for all $n \ge n_0$
$f(n) = \Omega(g(n))$	$f$ grows at least as fast as $g$	$c, n_0$ with $0 \le c\,g(n) \le f(n)$ for all $n \ge n_0$
$f(n) = \Theta(g(n))$	same growth rate	$c_1, c_2, n_0$ with $c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$
$f(n) = o(g(n))$	strictly slower (an upper bound that is not tight)	for every $c > 0$ there is an $n_0$ … $f(n) < c\,g(n)$
$f(n) = \omega(g(n))$	strictly faster	for every $c > 0$ … $f(n) > c\,g(n)$

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

Careful with little-o

The Lecture07 notation slide (Slide 6) calls $o$ a "tight upper bound". CLRS defines $o$ as an upper bound that is not tight ( $2n = o(n^2)$ , but $2n^2 \ne o(n^2)$ ). Use the CLRS meaning, and check with your instructor if an exam question depends on it.

Growth ladder (each grows strictly slower than the next):

1 \;<\; \log n \;<\; \sqrt n \;<\; n \;<\; n\log n \;<\; n^2 \;<\; n^3 \;<\; 2^n \;<\; 3^n \;<\; n! \;<\; n^n

Limit shortcut (for intuition and checking, not a replacement for a c/n₀ proof when one is asked): if $\lim_{n\to\infty} f(n)/g(n)$ is $0$ , then $f = o(g)$ ; if it is a constant $> 0$ , then $f = \Theta(g)$ ; if it is $\infty$ , then $f = \omega(g)$ .

Watch the ladder pull apart

$n$	$\log_2 n$	$n$	$n\log_2 n$	$n^2$	$2^n$
10	3.3	10	33	100	1 024
100	6.6	100	664	10 000	$\approx 1.3\times10^{30}$
1 000	10	1 000	9 966	1 000 000	$\approx 10^{301}$

What $f = O(g)$ looks like: take $f(n) = 3n + 7$ and $c\cdot g(n) = 4n$ .

$n$	1	3	5	6	7	8	10	100
$f(n) = 3n+7$	10	16	22	25	28	31	37	307
$4n$	4	12	20	24	28	32	40	400
$f \le 4n$ ?	❌	❌	❌	❌	✅	✅	✅	✅

Before $n_0 = 7$ , $f$ is bigger, and that's allowed. From $n_0$ on, $f$ stays under $c\cdot g$ forever, so $3n + 7 = O(n)$ .

$\Theta$ = sandwich: $c_1 g(n) \le f(n) \le c_2 g(n)$ . $f$ is trapped between two scaled copies of $g$ .

Common mistakes

Picking $n_0$ first, then a $c$ that only works for a different $n_0$ . State both and check them.
Thinking $O$ means "tight". $n = O(n^5)$ is true, just not useful. Use $\Theta$ when you mean tight.
Dropping a negative term in a lower bound, which makes $f$ bigger, not smaller.
Writing $O(2n^2 + 3)$ . Simplify to $O(n^2)$ .
The little-o slide wording (see the warning above).

Mastery check

Solve without hints, then explain

(a) Prove $4n^3 + 10n^2 + 5 = \Theta(n^3)$ with explicit $c_1, c_2, n_0$ .

(b) Prove $n^2 \ne O(5n + 2)$ .

Your mastery check

Not started

Solve the problem above with no hints, close the page and explain it out loud. Tick each step honestly.

Solved the mastery check with no hints

Said it in one sentence

Explained it with my own analogy

Walked through the steps of my own hand trace

Explained why it is correct / how fast it is

Named a trap a beginner would fall into

Status

Tick all six steps to unlock “Mastered”.

Which study mode worked for you?

Saved in this browser onlySee all my progress →

See it move

Desmos: plot $3x + 7$ and $4x$ and see them cross at $n_0 = 7$ .

References

Lecture07 Asymptotic Analysis: Slides 2–4 (growth classes), 6 (notation overview), 7–13 (Big-O and examples), 14–18 (Ω), 19–24 (Θ), 25 (when Θ isn't possible).
CLRS 4e Ch 3: §3.1 (O, Ω, Θ intuition), §3.2 (formal definitions, o and ω), §3.3 (standard functions).

6 · Asymptotic notation: O, Ω, Θ

Everyday analogyCopy Anchor Link

DefinitionsCopy Anchor Link

Common mistakesCopy Anchor Link

Mastery checkCopy Anchor Link

✅ Answers

See it moveCopy Anchor Link