Day 81 — Big-O formal

Updated

July 30, 2026

Day 81 — Big-O, \(\Omega\), \(\Theta\), \(o\), and \(\omega\) formally

Stage VIII · concept day
Goal: State formal asymptotic definitions; prove bounds with explicit witnesses \(C,n_0\); use limit tests; prove sum/product properties; avoid common notation abuses.

Why this matters

“\(O(n^2)\)” is not a vague English vibe — it is a quantified statement about eventual domination. Interview folklore and blogs often abuse the notation. Today you prove bounds the way a discrete math course expects, preparing Days 82–84.

Note

No labs. Code appears only as static fragments to describe cost, never as a programming exercise.

Theory

Setting

We compare functions \(f,g:\mathbb{N}\to\mathbb{R}\) (or eventually nonnegative real functions on \(\mathbb{N}\)). In algorithms, \(f(n)\) is often a runtime or operation count for input size \(n\). Asymptotics care about large \(n\), not \(n=1\) special cases.

Big-O (upper bound)

Definition (Big-O). We write \(f(n)=O(g(n))\) as \(n\to\infty\) if there exist constants \(C>0\) and \(n_0\in\mathbb{N}\) such that for all \(n\ge n_0\), \[ |f(n)| \le C\,|g(n)|. \] When \(f,g\ge 0\) eventually, this is \(f(n)\le C g(n)\) for \(n\ge n_0\).

Words. \(f\) grows at most as fast as \(g\), up to a constant factor, for large \(n\).

Set notation. \(O(g)=\{f:\exists C,n_0\ \forall n\ge n_0,\ |f|\le C|g|\}\). Writing \(f=O(g)\) means \(f\in O(g)\). The “\(=\)” is not symmetric: \(n=O(n^2)\) but \(n^2\neq O(n)\).

Quantifiers carefully: \(\exists C>0\ \exists n_0\ \forall n\ge n_0:\ |f(n)|\le C|g(n)|\).

Big-Omega (lower bound)

Definition (\(\Omega\)). \(f(n)=\Omega(g(n))\) if there exist \(c>0\) and \(n_0\) such that for all \(n\ge n_0\), \[ |f(n)| \ge c\,|g(n)|. \] Words. \(f\) grows at least as fast as \(g\) (up to a positive constant).

Duality. For positive functions, \(f=O(g)\) iff \(g=\Omega(f)\).

Big-Theta (tight bound)

Definition (\(\Theta\)). \(f(n)=\Theta(g(n))\) if \(f=O(g)\) and \(f=\Omega(g)\). Equivalently, \(\exists c_1,c_2>0\) and \(n_0\) such that for \(n\ge n_0\), \[ c_1 |g(n)| \le |f(n)| \le c_2 |g(n)|. \] Words. \(f\) and \(g\) have the same asymptotic growth rate up to constants.

Little-o and little-omega

Definition. \(f(n)=o(g(n))\) if for every \(\varepsilon>0\) there exists \(n_0\) such that for \(n\ge n_0\), \(|f(n)|\le \varepsilon |g(n)|\). Equivalently \(\lim_{n\to\infty} f(n)/g(n)=0\) when the limit exists.
\(f=\omega(g)\) means \(g=o(f)\).

Relation. \(f=o(g)\) implies \(f=O(g)\) but not conversely (\(n=O(n)\) but not \(o(n)\)). Little-o is a strictly slower growth statement.

Limit tests (practical)

When \(g(n)\neq 0\) and the limit exists in \([0,\infty]\):

Limit \(L=\lim f/g\) Conclusion (nonnegative case)
\(0\le L<\infty\) \(f=O(g)\)
\(0<L\le\infty\) \(f=\Omega(g)\)
\(0<L<\infty\) \(f=\Theta(g)\)
\(L=0\) \(f=o(g)\)
\(L=\infty\) \(f=\omega(g)\)

If the limit does not exist, witnesses or \(\limsup/\liminf\) arguments may still work.

Algebra of Big-O (nonnegative functions)

If \(f_1=O(g_1)\) and \(f_2=O(g_2)\), then:

  1. Sum: \(f_1+f_2=O(g_1+g_2)\) and also \(O(\max(g_1,g_2))\) when \(g_i>0\) (since \(g_1+g_2\le 2\max\)).
  2. Product: \(f_1 f_2=O(g_1 g_2)\).
  3. Transitivity: if \(f=O(g)\) and \(g=O(h)\) then \(f=O(h)\).
  4. Constants: for \(k>0\), \(k\cdot f=\Theta(f)\).
  5. Max: \(\max(f,g)=\Theta(f+g)\) for nonnegative \(f,g\).

Sum rule of thumb. If \(f=\Theta(n^2)\) and \(g=\Theta(n)\), then \(f+g=\Theta(n^2)\) — the faster-growing term dominates.

Proving \(f\neq O(g)\)

Negation. \(f\neq O(g)\) means: for every \(C>0\) and every \(n_0\), there exists \(n\ge n_0\) with \(|f(n)|>C|g(n)|\).
Strategy: for arbitrary \(C,n_0\), produce a large \(n\) violating the inequality.

Algorithm language

Saying “the algorithm is \(O(n^2)\)” usually means: there is a cost function \(T(n)\) with \(T(n)=O(n^2)\) in the worst case (or average case if specified). A \(\Theta\) claim is stronger and preferred when true. An \(O\) claim is not falsified by a faster true rate: if \(T(n)=\Theta(n)\), it is still correct that \(T(n)=O(n^2)\), but loose.

Common abuses

  1. Writing \(O(2n)\) as if better than \(O(n)\) — same class: \(O(2n)=O(n)\).
  2. \(T(n)=O(1)+O(n)\) without simplifying to \(O(n)\).
  3. Mixing average and worst case in one symbol without labels.
  4. Claiming \(f=O(g)\) from a plot at \(n\le 20\) only.
  5. Writing \(T(n)=O(f(n))+O(g(n))\) instead of \(O(f+g)\) then not simplifying.
  6. Treating \(O\) as \(\Theta\) in conversation (“is \(O(n\log n)\)” meaning tight).

Common algorithm bound catalogue (reminders)

Fragment / algorithm idea Typical tight class
Single loop \(1..n\) \(\Theta(n)\)
Double independent loops \(\Theta(n^2)\)
Binary search \(\Theta(\log n)\)
Comparison sort (optimal worst-case class) \(\Theta(n\log n)\)
Subset enumeration \(\Theta(2^n\cdot\mathrm{poly})\)

These are reminders, not substitutes for proofs on a concrete \(T(n)\).

Worked examples

Example 1 — Prove \(3n+5=O(n)\).
For \(n\ge 1\), \(3n+5\le 3n+5n=8n\). Take \(C=8\), \(n_0=1\).

Example 2 — Prove \(n=\Theta(n)\).
\(c_1=c_2=1\), \(n_0=1\): \(n\le n\le n\).

Example 3 — Prove \(n^2\neq O(n)\).
For any \(C,n_0\), pick \(n>\max(n_0,C)\); then \(n^2>C n\).

Example 4 — \(5n^2+3n+1=\Theta(n^2)\).
Upper: \(n\ge 1\) ⇒ \(5n^2+3n+1\le 5n^2+3n^2+n^2=9n^2\).
Lower: \(\ge 5n^2\). Take \(c_1=5\), \(c_2=9\), \(n_0=1\).

Example 5 — \(\log n=O(n)\).
\(\lim (\log n)/n=0\), so \(\log n=o(n)\) hence \(O(n)\). Explicitly \(\log_2 n\le n\) for \(n\ge 1\) after adjusting constant: \(\log_2 n=(\ln n)/\ln 2\le n/\ln 2\) for \(n\ge 1\) (actually \(\ln n\le n-1\)).

Example 6 — Limit test.
\(f(n)=n(n+1)/2\), \(g(n)=n^2\). \(f/g=\frac12+\frac{1}{2n}\to\frac12\), so \(f=\Theta(n^2)\).

Example 7 — Sum of costs.
Loop A \(\Theta(n)\), loop B \(\Theta(n^2)\), sequential: \(\Theta(n)+\Theta(n^2)=\Theta(n^2)\).

Example 8 — Little-o.
\(n=o(n^2)\) because \(n/n^2=1/n\to 0\). But \(n\neq o(n)\).

Example 9 — Product.
If \(f=O(n)\), \(g=O(n)\), then \(fg=O(n^2)\). Witnesses multiply: \(f\le C_1 n\), \(g\le C_2 n\) ⇒ \(fg\le C_1 C_2 n^2\).

Example 10 — Negation practice.
\(2^n\neq O(n^{100})\): \(2^n/n^{100}\to\infty\) (standard calculus / L’Hôpital \(100\) times, or known exponential vs poly).

Exercises

A. Definitions

  1. Write \(O\), \(\Omega\), \(\Theta\) with quantifiers from memory.
  2. Write \(o\) with quantifiers; contrast with \(O\).
  3. Explain why \(f=O(g)\) is not symmetric equality.
  4. Negate \(f=O(g)\) carefully with quantifiers.
  5. Show for positive \(f,g\): \(f=O(g)\Leftrightarrow g=\Omega(f)\).
  6. True or false: if \(f=O(g)\) and \(g=O(f)\) then \(f=\Theta(g)\). Prove.

B. Prove or disprove

  1. Prove \(7n+100=O(n)\) with explicit \(C,n_0\).
  2. Prove \(n=O(n^2)\) and \(n^2=\Omega(n)\).
  3. Prove \(n^2\neq O(n\log n)\) for \(\log\) base \(2\).
  4. Prove \(2^{n+1}=\Theta(2^n)\).
  5. Prove \(2^{2n}\neq O(2^n)\).
  6. Prove \(\frac{n(n-1)}{2}=\Theta(n^2)\).
  7. Prove \(\max(f,g)=\Theta(f+g)\) for nonnegative \(f,g\).
  8. Prove or discuss: \(O(f+g)=O(\max(f,g))\) as sets (nonnegative).
  9. Show \(n=o(n^2)\) but \(n\neq o(n)\).
  10. Analyze \(f(n)=n\) and \(g(n)=n+(-1)^n n/2\): is \(f=\Theta(g)\)?

C. Algorithmic interpretation

  1. Double loop for i=1..n: for j=1..n: O(1) — argue \(\Theta(n^2)\) body executions.
  2. If an algorithm is \(O(n^2)\) and \(\Omega(n^2)\) worst-case, what \(\Theta\) claim follows?
  3. Explain \(O(n^2)\) worst-case and \(O(n)\) best-case with two functions \(T_{\mathrm{worst}},T_{\mathrm{best}}\).
  4. Why drop constant factors and lower-order terms for large \(n\)?
  5. Give two examples where a looser \(O\) bound hides a practically important gap.

D. Properties and stretch

  1. Prove: if \(f_1=O(g_1)\), \(f_2=O(g_2)\) then \(f_1+f_2=O(\max(g_1,g_2))\) (nonnegative \(g_i\)).
  2. Prove: if \(f(n)\sim g(n)\) (ratio \(\to 1\)) then \(f=\Theta(g)\).
  3. Show there exist \(f,g>0\) with \(f\neq O(g)\) and \(g\neq O(f)\) (oscillatory).
  4. Prove \(n^k=o(2^n)\) for any fixed \(k\).
  5. Formalize polynomial time: \(T(n)=O(n^k)\) for some constant \(k\).

Deep dive — quantifier order drills

Correct \(O\): \(\exists C>0\ \exists n_0\ \forall n\ge n_0:\ |f|\le C|g|\).

Wrong variants students write:

  • \(\forall C\exists n_0\) — too strong (that is closer to little-o if \(C\) is arbitrary small).
  • \(\exists n_0\forall C\) — nonsense for \(O\).

Little-o: \(\forall\varepsilon>0\ \exists n_0\ \forall n\ge n_0:\ |f|\le\varepsilon|g|\).
The universal quantifier on \(\varepsilon\) is the difference that makes \(n=o(n)\) false.

Deep dive — proving sum/product rules

Sum. \(f_i\le C_i g_i\) for \(n\ge n_i\). Take \(n_0=\max n_i\), \(C=\max(C_1,C_2)\): \[ f_1+f_2\le C_1 g_1+C_2 g_2\le C(g_1+g_2)\le 2C\max(g_1,g_2). \]

Product. \(f_1 f_2\le C_1 C_2 g_1 g_2\) for \(n\ge\max n_i\) (nonnegative case).

Additional worked examples

Example 11 — \(n\log n=O(n^{1.5})\).
\((\log n)/n^{0.5}\to 0\), so eventually \(\log n\le n^{0.5}\), hence \(n\log n\le n^{1.5}\).

Example 12 — \(\Theta\) sandwich for \(n^3+100n\).
Lower: \(\ge n^3\). Upper: \(\le n^3+100n^3=101n^3\) for \(n\ge 1\).

Example 13 — Not \(\Theta\).
\(f(n)=n\) if \(n\) even, \(n^2\) if \(n\) odd: \(f\neq O(n)\) and careful analysis vs \(n^2\).

Example 14 — Algorithm false friend.
“Two nested loops” is not automatically \(n^2\) if bounds are \(i=1..n\), \(j=1..i\) still \(\Theta(n^2)\), but \(j=1..\log n\) is \(\Theta(n\log n)\).

Example 15 — Limit fails to exist.
\(f(n)=n(2+\sin n)\), \(g(n)=n\): ratio oscillates in \([1,3]\), still \(\Theta(n)\).

More exercises

  1. Prove \(100n+7=O(n)\) with \(C=101\), find minimal integer \(n_0\) for that \(C\).
  2. Prove \(\log(n!)=O(n\log n)\) without Stirling (bound \(\log(n!)\le n\log n\)).
  3. Prove \(\log(n!)=\Omega(n\log n)\) by \(\log(n!)\ge (n/2)\log(n/2)\).
  4. Show \(O(n)+O(n^2)=O(n^2)\) as sets of functions (nonnegative).
  5. Negate \(f=\Omega(g)\) carefully.
  6. CS: explain why “is \(O(n^2)\)” in an interview should often be upgraded to \(\Theta\) discussion.

Selected mini-solutions

  1. \(7n+100\le 7n+100n=107n\) for \(n\ge 1\).
  2. \(2^{n+1}=2\cdot 2^n\).
  3. \(2^{2n}/2^n=2^n\to\infty\).
  4. Repeated L’Hôpital or ratio \((n+1)^k/2^{n+1}\div(n^k/2^n)\to 1/2\).

Common pitfalls

Pitfall Fix
Treating \(O\) as \(\Theta\) \(O\) is only upper bound
Hiding \(n_0\) dependence on \(C\) Order is \(\exists C\exists n_0\)
Proving for one \(n\) only Need all \(n\ge n_0\)
Using \(\log\) without base Bases differ by constants: \(\Theta\) same
Saying “\(O(2n)\) better than \(O(n)\)” Same class
Confusing \(o\) quantifiers with \(O\) \(\forall\varepsilon\) vs \(\exists C\)

Study notes — asymptotic cheat card

Want Means
\(f=O(g)\) \(\exists C,n_0:\ n\ge n_0\Rightarrow |f|\le C|g|\)
\(f=\Omega(g)\) \(\exists c,n_0:\ |f|\ge c|g|\)
\(f=\Theta(g)\) both \(O\) and \(\Omega\)
\(f=o(g)\) \(\forall\varepsilon\exists n_0:\ |f|\le\varepsilon|g|\)
Limit \(L\in(0,\infty)\) \(\Theta\)
Limit \(0\) \(o\) (hence \(O\))
Limit \(\infty\) \(\omega\) (hence \(\Omega\))

Synthesis — asymptotics workout

S1. Write \(O,\Omega,\Theta,o\) with full quantifiers from memory.

S2. Prove \(4n^2+3n+2=\Theta(n^2)\) with explicit \(c_1,c_2,n_0\).

S3. Prove \(n\log n\neq O(n)\) and \(n\log n=O(n^{1.5})\).

S4. Prove \(2^{n}\neq O(n^{100})\) via limits or ratios.

S5. Negate \(f=O(g)\); use it to show \(n^2\neq O(n)\).

S6. Prove sum rule: \(f=O(n)\), \(g=O(n^2)\) ⇒ \(f+g=O(n^2)\).

S7. Explain \(T=O(n^2)\) vs \(T=\Theta(n^2)\) for a nested loop.

S8. Limit test: classify \(f(n)=n(n+1)(n+2)/6\) vs \(g(n)=n^3\).

Checkpoint

  • Can write \(O/\Omega/\Theta/o\) with quantifiers
  • Can prove simple polynomial bounds with explicit \(C,n_0\)
  • Can prove \(n^2\neq O(n)\) style negations
  • Can use limit tests
  • Can apply sum/product rules
  • Exercises A–C done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — limit test with proof obligations

Proposition. Suppose \(f,g>0\) and \(L=\lim_{n\to\infty}f(n)/g(n)\) exists in \([0,\infty]\).

  1. If \(L<\infty\) then \(f=O(g)\).
  2. If \(L>0\) then \(f=\Omega(g)\).
  3. If \(0<L<\infty\) then \(f=\Theta(g)\).
  4. If \(L=0\) then \(f=o(g)\).
  5. If \(L=\infty\) then \(f=\omega(g)\).

Proof of (1). If \(L<\infty\), the sequence \(f/g\) is eventually bounded, say \(f/g\le C\) for \(n\ge n_0\) (e.g. \(C=L+1\) if \(L\) finite). Thus \(f\le C g\).
Proof of (4). \(L=0\) means \(\forall\varepsilon>0\) eventually \(f/g<\varepsilon\), which is exactly \(f=o(g)\).

When the limit fails. Use \(\limsup\) for \(O\) and \(\liminf\) for \(\Omega\), or construct explicit witnesses. Example: \(f(n)=n(2+\sin n)\) still \(\Theta(n)\) even though \(f/n\) has no single limit if one worries about \(\sin n\) density — actually \(\sin n\) is dense in \([-1,1]\) but bounded, so \(1\le 2+\sin n\le 3\) gives sandwich.

Deeper theory — polynomial \(\Theta\) class

Theorem. If \(p(n)=a_d n^d+\cdots+a_0\) with \(a_d\neq 0\) and real coefficients, then \(p(n)=\Theta(n^d)\) as \(n\to\infty\) through positives large enough that \(p\) keeps the sign of \(a_d\) (for algorithms, usually \(a_d>0\) and \(p>0\)).

Proof sketch. Factor \(p(n)=n^d\bigl(a_d+a_{d-1}/n+\cdots+a_0/n^d\bigr)\). The expression in parentheses tends to \(a_d\neq 0\), so it is bounded between \(|a_d|/2\) and \(2|a_d|\) for large \(n\). Multiply by \(n^d\).

Worked examples — witness hunting

Example 16 — \(n^2+100n=\Theta(n^2)\) with explicit constants.
Upper: for \(n\ge 1\), \(n^2+100n\le n^2+100n^2=101n^2\).
Lower: \(n^2+100n\ge n^2\). So \(c_1=1\), \(c_2=101\), \(n_0=1\).

Example 17 — Prove \(\log_2(n!)=O(n\log_2 n)\).
\(n!\le n^n\) ⇒ \(\log_2(n!)\le n\log_2 n\). \(C=1\), \(n_0=2\).

Example 18 — Prove \(\log_2(n!)=\Omega(n\log_2 n)\).
For \(n\ge 2\), \(n!\ge (n/2)^{n/2}\) (product of the largest \(n/2\) factors each \(\ge n/2\)). Thus \(\log_2(n!)\ge (n/2)\log_2(n/2)=\Omega(n\log n)\).

Example 19 — Nested loop count.
for i = 1..n: for j = 1..i: O(1) executes \(\sum_{i=1}^n i=n(n+1)/2=\Theta(n^2)\) times — not \(\Theta(n)\) just because the inner bound depends on \(i\).

Extra exercises — asymptotic proofs

  1. Prove \(5n^3+2n=\Theta(n^3)\) with \(c_1,c_2,n_0\).
  2. Prove \(n^{1.1}\neq O(n\log n)\).
  3. Prove \(3^{n}=O(4^n)\) and \(4^n\neq O(3^n)\).
  4. Show \(O(n)\cdot O(n)=O(n^2)\) as a product of classes (nonnegative functions).
  5. Negate \(f=\Theta(g)\) carefully (two-sided failure modes).
  6. For \(T(n)=2T(n/2)+n\) with \(T(1)=1\) on powers of two, prove by induction \(T(n)=n\log_2 n+n\) (exact), hence \(\Theta(n\log n)\).
  7. Explain why \(O(1)\) memory and \(O(n)\) time are independent claims.
  8. CS interview hygiene: rewrite “our API is \(O(n^2)\)” as a precise statement about a cost model.

Mini-solutions (selected)

  1. \(n^{1.1}/(n\log n)=n^{0.1}/\log n\to\infty\).
  2. \((3/4)^n\to 0\) so \(3^n=o(4^n)\); reverse ratio \(\to\infty\).
  3. Inductive step: \(T(2m)=2T(m)+2m=2(m\log_2 m+m)+2m=2m\log_2 m+4m=(2m)\log_2(2m)+2m\).

Closing synthesis card

Symbol Quantifiers Limit form
\(O\) \(\exists C\exists n_0\) \(L<\infty\)
\(\Omega\) \(\exists c\exists n_0\) \(L>0\)
\(\Theta\) both \(0<L<\infty\)
\(o\) \(\forall\varepsilon\exists n_0\) \(L=0\)

Always produce witnesses on exams unless a clean limit is given.

Tomorrow

Day 82 — Growth classes: ranking \(\Theta\) families.