O, Ω, Θ
For eventually nonnegative functions, O is an eventual constant-factor upper bound, Ω a lower bound, and Θ both.
Find a concept
REFERENCE SHEET
Asymptotics & recurrences
State the input-size measure and computational model before counting operations.
Before this Proof techniques
f ∈ O(g) ⇔ ∃c>0, n₀: 0≤f(n)≤c g(n) for all n≥n₀
Definitions
Input length
The size of an encoded input. An integer N written in binary needs Θ(log(N+1)) bits, so polynomial in N need not mean polynomial in input length.
Recurrence
An equation or inequality relating a running time to smaller input sizes, together with base-case costs.
Key theorems
Master theorem, polynomial-gap cases
For T(n)=aT(n/b)+f(n), a≥1 and b>1 constants, compare f(n) with nᵖ, p=log_b a. If f=O(nᵖ⁻ε), then T=Θ(nᵖ). If f=Θ(nᵖ), then T=Θ(nᵖ log n). If f=Ω(nᵖ⁺ε) and af(n/b)≤cf(n) for some c<1 eventually, then T=Θ(f(n)). Assume the usual positive constant base costs and nonnegative work.
Geometric-series analysis
Repeated halving gives logarithmic recursion depth. A recursion tree must also count the number and cost of nodes at each depth.
Notable applications
Scalability
Distinguish growth rates before optimizing constant factors.
Divide and conquer
Analyze mergesort, binary search, and recursive numerical algorithms.
Work it out
Try before revealing01 / Solve
Find a tight bound for T(n)=2T(n/2)+n with T(1)=1 and n a power of 2.
Hint
Each recursion level does total work n.
Solution
There are log₂n internal levels, each costing n, and n leaves of cost 1. Thus T(n)=n log₂n+n=Θ(n log n).
02 / Classify
An algorithm loops N times on an integer N supplied in binary. Is O(N) polynomial in the input bit length?
Hint
Compare N with the bit length m.
Solution
Not in general. For an m-bit positive integer, N can be as large as 2ᵐ−1. The loop can therefore take exponential time in m.
Connect the ideas
Build on this
These sheets use this topic as a prerequisite.
Go deeper
Further reading and full-length treatments: