Recipe

Prove a Big-O bound from the definition

Use when: you're given two functions f(n) and g(n) and asked to prove f(n)=O(g(n)) directly, by exhibiting witnesses, rather than just stating the bound

Goal: a specific constant c>0 and threshold n0, verified to satisfy f(n) <= c*g(n) for every n >= n0

Taught in Proving a Big-O bound

Quick recipe

Choose a candidate constant c
Solve the inequality for n
Set n0 from the solved inequality
Verify the inequality for an arbitrary n at or past n0
State the witnesses

1
Pick a specific value for $c$ , usually by inspecting the leading term of $f(n)$ and rounding its coefficient up.

Example

For $f(n)=3n+5$ and $g(n)=n$ , choose $c=8$ , comfortably above the leading coefficient $3$ .
- $f(n)$ has one dominant term for large $n$ — choose $c$ a bit above that term's own coefficient.
- $f(n)$ is a sum of several terms with similar growth rates — choose $c$ as the sum of every coefficient, which always overshoots enough to cover them all at once.
Why: the constants are chosen first, then verified afterward; a Big-O proof never needs the tightest possible $c$ , only one that provably works.
2
Set up $f(n)\le c\cdot g(n)$ with the chosen $c$ already substituted, then solve the resulting inequality for $n$ directly, the same way any algebraic inequality is solved.

Example

$3n+5\le 8n$ rearranges to $5\le 5n$ , which rearranges to $n\ge1$ .

Why: solving for $n$ actually finds a working threshold, rather than guessing one and hoping it holds.
3
Read the threshold directly off the solved inequality and declare it as $n_0$ .

Why: $n_0$ only needs to be one value that works, past which the inequality holds for every larger $n$ too.
4
Confirm $f(n)\le c\cdot g(n)$ holds for an arbitrary $n\ge n_0$ , not just the boundary value, by checking that the same rearrangement from the previous step goes through for any such $n$ .

Example

At $n=1$ : $3(1)+5=8$ and $8(1)=8$ , equal exactly at the boundary; for any $n>1$ the identical rearrangement, $3n+5\le8n \iff 5\le5n$ , holds with room to spare.

Why: an inequality checked only at one value has not established the claim for every $n$ in the range; the algebra has to hold for an arbitrary $n$ .
5
Conclude $f(n)=O(g(n))$ , naming the specific $c$ and $n_0$ that were found.

Why: a Big-O claim is only proved once both witnesses are stated explicitly, not left implicit in the algebra.

Common mistakes

Choosing $c$ so small the inequality never actually holds, not even eventually.
Checking the inequality only at $n=n_0$ instead of confirming it for an arbitrary $n\ge n_0$ .
Solving the inequality in the wrong direction, finding where $f(n) \ge c\cdot g(n)$ instead of $\le$ .
Treating one specific pair of witnesses as "the" answer, when any valid pair proves the claim.