Foundations — Tight bounds — Θ notation; lower bounds — Ω notation

This page assumes nothing. Before you meet $\Theta$ and $\Omega$ in the parent topic, every squiggle those definitions use gets built here from the ground up, in the order that each one depends on the last.

0. The raw picture: what is a "cost curve"?

Before any symbol, here is the object everything else talks about.

Imagine you run an algorithm on inputs of size 1, 2, 3, … and for each size you write down how much work it does (how many steps, comparisons, or operations). Plot those dots: horizontal axis = input size, vertical axis = work done. Connect them and you get a curve that climbs.

1. Functions and the "$(\cdot )$" notation

The single most-used piece of notation is writing $f(n)$, $g(n)$, $cg(n)$. If parentheses-after-a-letter is new, read this.

2. Reference shapes: $n$, $n^2$, $\log n$, $n\log n$

The yardsticks $g$ are always simple growth shapes. You must recognise them by eye.

3. Two limiting words: $\forall$ and $\exists$

The definitions in the parent lean on two logic symbols. Here they are, in plain speech.

4. The threshold $n_0$ — "eventually"

5. The constant $c$ — "same shape, ignore the dial"

6. Now the three bounds are just three sandwiches

With $f$, $g$, $c$, $n_0$, $\forall$, $\exists$ all built, the parent's definitions read cleanly. Here is what each one looks like on the axes.

• $O$: your curve stays under the dashed reference — a lid.
• $\Omega$: your curve stays over the dashed reference — a floor.
• $\Theta$: your curve is squeezed between two dashed copies of the same reference — pinned to that shape.

That's the entire topic. Everything else (the limit shortcut, the worked examples) is machinery for finding the right $g$ and the constants.

7. The "$=$" that isn't equals

8. How these feed the topic

Each foundation on the left is a prerequisite for the sandwich definitions, which then split into $O$, $\Omega$, and finally the tight $\Theta$. If any left-hand box is fuzzy, the parent topic will feel like magic — go back and firm it up.

Related vault topics

• Big-O notation — upper bounds — the ceiling half, in full
• Asymptotic comparison of functions — the $n\to \infty$ mindset and little-oh siblings
• Limits and L'Hôpital's rule — powers the limit shortcut for testing bounds
• Best, worst, and average case analysis — the separate axis of which input you pick
• Decision trees and sorting lower bound — where the $\log n$ shape earns its keep
• Master Theorem — machinery that outputs $\Theta$ for recurrences

Equipment checklist