Tight bounds — Θ notation; lower bounds — Ω notation: Worked examples

This is the drill room for the parent topic. The parent gave you the definitions; here we run them through every kind of situation a problem can throw at you, one worked case per cell, so you never meet an unfamiliar shape in an exam.

Before we start, one reminder of the three definitions we are going to apply (never assume — always earn):

The scenario matrix

Every complexity-bound problem you will ever be asked is one of these cells. The examples below are labelled with the cell they close.

Cell	What it tests	Example
A. Polynomial + junk	Drop lower-order terms, keep the top	Ex 1
B. Ceiling holds, floor fails	$O$ yes, $Ω$ no → strictly smaller ( $o$ )	Ex 2
C. Floor holds, ceiling fails	$Ω$ yes, $O$ no → strictly larger ( $ω$ )	Ex 3
D. Log / non-polynomial shapes	$lo g n$ , $n lo g n$ ranking	Ex 4
E. The limit shortcut (all 3 outcomes: $0$ , finite, $\infty$ )	L'Hôpital-style test	Ex 5
F. Degenerate / zero-ish input	constant $f$ , $g = 1$ , or $f \equiv 0$	Ex 6
G. No single $Θ$ exists	best ≠ worst in order	Ex 7
H. Word problem (real algorithm)	translate code → $T (n)$ → bound	Ex 8
I. Exam twist (sum of unlike terms)	$2^{n}$ vs $n^{100}$ , dominance	Ex 9

We cover all nine. Signs never go negative here (running times are $\geq 0$ ), so our "quadrant" analogue is instead which term dominates and which of ${0, finite, \infty}$ the ratio lands on — those are the branches we must exhaust.

Cell A — Polynomial with lower-order junk

Worked example Ex 1 · Show

$4 n^{3} + 100 n^{2} + 9 = Θ (n^{3})$ Forecast: guess the answer before reading. Which power wins as $n \to \infty$ ? Write down $c_{1}, c_{2}, n_{0}$ in your head.

Upper (ceiling). For $n \geq 1$ : $100 n^{2} \leq 100 n^{3}$ and $9 \leq 9 n^{3}$ , so $4 n^{3} + 100 n^{2} + 9 \leq 4 n^{3} + 100 n^{3} + 9 n^{3} = 113 n^{3} .$ Why this step? Replacing each small term by an $n^{3}$ -sized term only makes the right side bigger, so the $\leq$ is guaranteed. This gives $c_{2} = 113$ .
Lower (floor). All added terms are positive, so $4 n^{3} + 100 n^{2} + 9 \geq 4 n^{3} (n \geq 0) .$ Why this step? Dropping positive stuff only shrinks the value, giving a clean floor. This gives $c_{1} = 4$ .
Combine. $4 n^{3} \leq f (n) \leq 113 n^{3}$ for $n \geq 1$ , which is exactly the $Θ$ sandwich.

Verify: at $n = 10$ , $f = 4000 + 10000 + 9 = 14009$ ; check $4 \cdot 1 0^{3} = 4000 \leq 14009 \leq 113 \cdot 1 0^{3} = 113000$ . ✓ Both sides straddle it, so $f = Θ (n^{3})$ with $c_{1} = 4, c_{2} = 113, n_{0} = 1$ . ∎

Cell B — Ceiling holds, floor fails ( $f = o (g)$ )

Worked example Ex 2 · Show

$n lo g_{2} n = O (n^{2})$ but not $Ω (n^{2})$ Forecast: does $n lo g n$ eventually stay under a scaled $n^{2}$ ? And could a floor $c n^{2}$ ever sit under $n lo g n$ forever?

Ceiling. For $n \geq 2$ , $lo g_{2} n \leq n$ , so $n lo g_{2} n \leq n \cdot n = n^{2}$ . Take $c = 1$ : this is $O (n^{2})$ . Why this step? $lo g_{2} n$ grows slower than $n$ , so multiplying by $n$ keeps us under $n^{2}$ .
Floor attempt. Suppose $c n^{2} \leq n lo g_{2} n$ for all large $n$ . Divide by $n > 0$ : $c n \leq lo g_{2} n$ . Why this step? We isolate the shapes: the left grows linearly, the right logarithmically. A line eventually beats any log, so no fixed $c > 0$ survives.
Conclude. Ceiling yes, floor no $\Rightarrow$ strictly smaller order: $n lo g_{2} n = o (n^{2})$ .

Verify: the limit $lim_{n \to \infty} \frac{n lo g _{2} n}{n ^{2}} = lim \frac{lo g _{2} n}{n} = 0$ , confirming $O$ not $Ω$ . Sanity at $n = 1024$ : $n lo g_{2} n = 1024 \cdot 10 = 10240$ vs $n^{2} \approx 1.05 \times 1 0^{6}$ — tiny in comparison. ✓ ∎

Look at the ratio curve in the figure: it slides toward $0$ , never levelling off.

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

Cell C — Floor holds, ceiling fails ( $f = ω (g)$ )

Worked example Ex 3 · Show

$2^{n} = Ω (n^{10})$ but not $O (n^{10})$ Forecast: exponential vs a big polynomial — who wins? (This is the classic exam trap: $n^{10}$ looks huge for small $n$ .)

Small- $n$ warning. At $n = 10$ : $2^{10} = 1024$ but $1 0^{10} = 10, 000, 000, 000$ . The polynomial is way ahead here! Why mention this? It shows why $n_{0}$ matters — the true trend only appears later.
Floor. Eventually $2^{n}$ overtakes and stays above any constant times $n^{10}$ ; that crossover is our $n_{0}$ . So $2^{n} = Ω (n^{10})$ .
Ceiling fails. No constant $c$ gives $2^{n} \leq c n^{10}$ for all large $n$ , because the ratio $\frac{2 ^{n}}{n ^{10}} \to \infty$ . So not $O$ .
Conclude: strictly larger order — $2^{n} = ω (n^{10})$ .

Verify: find the crossover $n_{0}$ where $2^{n} > n^{10}$ first holds. Numerically it flips near $n \approx 59$ ( $2^{59} \approx 5.76 \times 1 0^{17}$ vs $5 9^{10} \approx 5.11 \times 1 0^{17}$ ). At $n = 59$ the exponential has just won and never loses again. ✓ ∎

The figure shows the polynomial ahead early, then the exponential blasting past.

Cell D — Logarithmic / non-polynomial shapes

Cell E — The limit shortcut, all three outcomes

Cell F — Degenerate / near-zero inputs

Worked example Ex 6 · The constant-cost and zero-cost edge cases

Forecast: what is the growth class of an algorithm that always does exactly $7$ steps? And of one whose cost is literally $0$ ?

Constant cost $f (n) = 7$ . Compare with $g (n) = 1$ . Floor: $7 \geq 1 \cdot 1$ . Ceiling: $7 \leq 7 \cdot 1$ . So $c_{1} = 1, c_{2} = 7$ , and $7 = Θ (1)$ . Why this step? $Θ (1)$ is the formal way to say "constant time" — the reference $g = 1$ is the flat function.
Is $7 = Θ (n)$ ? No: the ratio $\frac{7}{n} \to 0$ , so $7 = o (n)$ (a constant is strictly smaller than any growing function).
Zero cost $f (n) \equiv 0$ . The definitions demand $c g (n) \leq f (n)$ i.e. $c g (n) \leq 0$ . For a positive $g$ and $c > 0$ this fails, so $0$ is $O (g)$ for any $g$ but not $Ω (g)$ unless $g \equiv 0$ . Why this step? The " $0 \leq$ " guard in the definition is doing real work here — a genuinely zero function has no positive floor.

Verify: ratio $7/1 = 7$ (finite nonzero → $Θ (1)$ ✓); ratio $7/ n$ at $n = 1000$ is $0.007 \to 0$ (so $o (n)$ ✓). ∎

Cell G — When NO single $Θ$ exists

Worked example Ex 7 · Insertion sort's whole runtime has no single

$Θ$ Forecast: best case is $Θ (n)$ (already-sorted), worst is $Θ (n^{2})$ (reverse-sorted). Can one $Θ$ cover the whole runtime?

Best case. Already sorted: each element checks its left neighbour once — $n - 1$ comparisons $= Θ (n)$ .
Worst case. Reverse sorted: element $i$ shifts past all $i$ predecessors — $\sum_{i = 1}^{n - 1} i = \frac{n ( n - 1 )}{2} = Θ (n^{2})$ . Why this step? The triangular sum $\frac{n ( n - 1 )}{2}$ is a degree-2 polynomial, hence $Θ (n^{2})$ by Cell A logic.
Conclude. The runtime function ranges over an order gap ( $n$ up to $n^{2}$ ), so no single $g$ pins it from both sides. We can only say the whole runtime is $O (n^{2})$ and $Ω (n)$ — not $Θ$ of anything single. (See Best, worst, and average case analysis.)

Verify: worst-case comparisons at $n = 5$ : $\frac{5 \cdot 4}{2} = 10$ ; best-case at $n = 5$ : $n - 1 = 4$ . Since $10 \neq = c \cdot 4$ for a fixed $c$ across all $n$ (their ratio $\frac{n ( n - 1 ) /2}{n - 1} = \frac{n}{2} \to \infty$ ), the two cases live in different orders. ✓ ∎

Cell H — Word problem: bound a real loop

Worked example Ex 8 · Nested-loop counting

A function runs the inner line once for every pair $(i, j)$ with $1 \leq j \leq i \leq n$ :

for i in 1..n:
    for j in 1..i:
        work()      # 1 unit

Forecast: guess the total number of work() calls as a function of $n$ , and its $Θ$ class.

Count exactly. Inner loop runs $i$ times, so total $T (n) = \sum_{i = 1}^{n} i = \frac{n ( n + 1 )}{2}$ . Why this step? Sum of the first $n$ integers — the same triangular formula, giving the exact call count.
Expand. $\frac{n ( n + 1 )}{2} = \frac{n ^{2}}{2} + \frac{n}{2}$ . Top term is $\frac{1}{2} n^{2}$ .
Bound. Floor: $\frac{n ^{2}}{2} \leq T (n)$ . Ceiling: $T (n) \leq \frac{n ^{2}}{2} + \frac{n ^{2}}{2} = n^{2}$ for $n \geq 1$ . So $c_{1} = \frac{1}{2}, c_{2} = 1$ .
Conclude: $T (n) = Θ (n^{2})$ .

Verify (units + plug-back): work() calls are dimensionless counts. At $n = 4$ : $T = \frac{4 \cdot 5}{2} = 10$ , and $\frac{16}{2} = 8 \leq 10 \leq 16 = n^{2}$ . ✓ ∎

Cell I — Exam twist: sum of wildly unlike terms

Worked example Ex 9 · Show

$n^{100} + 2^{n} = Θ (2^{n})$ Forecast: a polynomial of degree 100 plus an exponential. Which one is the "shape," and which is junk?

Identify the dominant term. From Ex 3, $2^{n} = ω (n^{k})$ for any fixed $k$ — including $k = 100$ . So $2^{n}$ dominates. Why this step? Exponential beats every polynomial eventually; the huge degree $100$ only delays $n_{0}$ , it never changes the class.
Floor. $n^{100} + 2^{n} \geq 2^{n}$ (extra term positive), so $c_{1} = 1$ .
Ceiling. For $n \geq n_{0}$ where $n^{100} \leq 2^{n}$ : $n^{100} + 2^{n} \leq 2^{n} + 2^{n} = 2 \cdot 2^{n}$ , so $c_{2} = 2$ . Why this step? Once the poly is below the exponential, the whole sum is under twice the exponential.
Conclude: $2^{n} \leq f (n) \leq 2 \cdot 2^{n} \Rightarrow f = Θ (2^{n})$ .

Verify: find where $n^{100} \leq 2^{n}$ takes hold — near $n \approx 1000$ (since $100 lo g_{2} n \leq n$ requires $n$ large). At $n = 1000$ : $lo g_{2}$ check $100 \cdot lo g_{2} 1000 = 996.6 \leq 1000$ . ✓ So for $n \geq 1000$ , $2^{n} \leq f \leq 2 \cdot 2^{n}$ . ∎

Recall Quick self-test — cover the answers

Which cell: $5 n^{2} + 3 = Θ (?)$ ::: $Θ (n^{2})$ (Cell A). Which cell: $lim f / g = \infty$ tells you? ::: $f = Ω (g)$ not $O (g)$ , i.e. $ω (g)$ (Cell C/E). Does insertion sort have one $Θ$ for its full runtime? ::: No — best $Θ (n)$ , worst $Θ (n^{2})$ (Cell G). Class of a function that always costs $7$ steps? ::: $Θ (1)$ (Cell F). Does the log base change the class? ::: No, $lo g_{a} n = Θ (lo g_{b} n)$ (Cell D).

Connections

Big-O notation — upper bounds — the ceiling half we lean on in every example.
Best, worst, and average case analysis — the other axis, central to Cell G.
Asymptotic comparison of functions — the $o$ / $ω$ verdicts in Cells B, C, F, I.
Limits and L'Hôpital's rule — powers the ratio test of Cell E.
Master Theorem — gives $Θ$ for recurrences (the next drill).
Decision trees and sorting lower bound — the problem-level $Ω$ .