STEP-BY-STEP LESSON · §11.2
Big-O, Big-Omega, and Big-Theta Notations
Prove growth order using explicit bounds.
Before you begin
Using an inequality bound
A lower bound is no greater than the quantity; an upper bound is no smaller. Multiplying an inequality by a positive number preserves its direction. To compare formulas eventually, one set of constants must work for every input past a stated threshold.
Function, domain and codomain
A function assigns exactly one permitted output to every input in its domain. Its codomain is the declared output set; some members of that set may never be reached. The same formula on another domain or codomain can have different properties. f(x) names the output at x; it is not multiplication.
Symbols
- O(g)
- asymptotic upper bound
- Ω(g)
- asymptotic lower bound
- Θ(g)
- matching upper and lower bounds
- c,C,n₀
- Fixed positive lower/upper constants and an input threshold; none depends on n
Definitions and notation for this topic
Big O, big Omega and big Theta
f∈O(g); f∈Ω(g); f∈Θ(g)
For eventually nonnegative functions f(n) and eventually positive g(n) on integer inputs: O(g) means f(n)≤C g(n) for all n≥n₀; Ω(g) means c g(n)≤f(n) for all n≥n₀; Θ(g) requires both bounds. Suitable constants c,C>0 and a threshold n₀ must exist and be independent of n.
Big O alone is an upper bound, not necessarily a tight order. The common shorthand f=O(g) means membership in a class of bounds, not equality with one function. Ω(g) is unrelated to the sample-space name Ω.
Separate glossary example
For n≥1, 3n²≤3n²+2n+1≤6n², so 3n²+2n+1∈Θ(n²), using c=3,C=6,n₀=1.
Step by step
Step 1 / 6
Compare beyond a threshold
For nonnegative functions, f=O(g) if some C>0 and n₀ make f(n)≤Cg(n) for all later n.
A constant factor and a finite initial segment do not determine the asymptotic class.
Worked example
Prove 2n²+3n+1=Θ(n²) for integers n≥1.
- Below, 2n²+3n+1≥2n².
- For n≥1, n≤n² and 1≤n²; the upper bound is 6n².
- Take c=2, C=6, n₀=1.
Optional self-check
Why does n=O(n²) not also establish n=Θ(n²)?
Show answer
O gives only an upper bound. A positive constant c with cn²≤n for all large n would require c≤1/n forever, which no fixed c>0 can satisfy.