Math101 · Independent Ontario learning library
Math101learn.math101.caBig O Notation
A precise guide to asymptotic upper bounds, comparison rules, proofs, and the limits of Big O claims.
Precise definition
For eventually non-negative functions $f$ and $g$, the statement $f(n)=O(g(n))$ means there exist constants $c>0$ and $n_0$ such that $0\le f(n)\le c g(n)$ for every $n\ge n_0$. Big O is an asymptotic upper bound, not automatically a tight bound or an equality of functions.
Notation and mathematical language
Use $O(g)$ for an upper bound, $\Omega(g)$ for a lower bound, and $\Theta(g)$ when both hold. The variable $n$ must denote a specified input size. Constants $c$ and $n_0$ are witnesses in a proof; they may depend on the functions but not on $n$.
Conceptual picture
Asymptotic notation deliberately ignores fixed multiplicative factors and finite initial behaviour. It answers how resource use scales when inputs grow, not exactly how long a particular machine takes. Thus $3n^2+10n+7$ and $n^2$ share a quadratic growth class even though their measured times differ.
Conditions and key results
To prove an $O$ claim, exhibit valid witnesses and an inequality for all sufficiently large $n$. Common algebraic simplifications require non-negative terms. Worst-case, average-case, and best-case bounds describe different functions and must not be interchanged without analysis; logarithm bases differ only by a positive constant.
A reliable strategy
- Define what $n$ measures and which operation or resource is being counted.
- Simplify sums and products using eventual upper bounds while retaining the dominant growth term.
- For a formal proof, choose $n_0$ and a constant $c$, then verify the defining inequality.
- State whether the result is worst-case, average-case, best-case, or an input-specific observation.
Fully worked example
Interpretation and application
Complexity classes guide algorithm selection: replacing a quadratic scan with an $n\log n$ method can dominate hardware improvements at large scale. Constants and cache effects still matter for practical sizes, so an asymptotic comparison should accompany, not replace, measurement on representative inputs.
Common mistakes
Verification and reasonableness
- Substitute the proposed $c$ and $n_0$ back into the defining inequality.
- Compare ratios or dominant terms only as intuition, then supply a bound when a proof is requested.
- Check that changing the input representation has not changed what the variable $n$ means.
Practice
- Give witnesses proving $2n+5=O(n)$ for $n\ge1$.
- Is $n=O(n^2)$? Is the bound tight?
- Order $\log n$, $n\log n$, and $2^n$ by eventual growth.
Answers and brief solutions
- $2n+5\le7n$, so $c=7$ and $n_0=1$ work.
- Yes for $n\ge1$, but it is not tight; $n=\Theta(n)$.
- $\log n<n\log n<2^n$ for sufficiently large $n$.
Further deduction
For positive functions, a finite nonzero limit $\lim_{n\to\infty}f(n)/g(n)=L$ implies $f=\Theta(g)$, but the limit test is sufficient rather than the definition. A ratio that oscillates can still yield a valid $\Theta$ bound when it remains between positive constants eventually. Closure rules follow from witnesses: if $f=O(g)$ and $h=O(k)$, then $f+h=O(g+k)$ and $fh=O(gk)$ under eventual non-negativity. These rules must be applied to the same limiting regime and compatible input-size variable.
Related topics
Try it yourself
Hints are part of learning. Open one whenever it makes the next step feel possible.
For $n\ge1$, what integer $c$ makes $6n+4\le cn$ using the smallest whole-number choice?
- For $n\ge1$, $6n+4\le6n+4n$.
- Thus $6n+4\le10n$, so $c=10$ works with $n_0=1$.
End of lesson
Nice work making it this far.
Understanding grows through return visits. Save this lesson, try the practice, or continue when you are ready.
