Asymptotic Notation & Big-O Proofs
O, Ω, Θ, o and ω describe how fast T(n) grows for large n. Learn the definitions, the order of growth, and how to prove f(n) = O(g(n)) by finding c and k.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
T(n) = 4n + 3 and T(n) = 7n + 100 look different, but for a million items both grow in a straight line. Asymptotic notation throws away constants and small terms and keeps only the shape of growth for large n. Think of describing a car as “fast” rather than “214.3 km/h”.
The five notations
Let f(n) be the running time and g(n) a simple function like n or n².
| Notation | Read as | Meaning | Like |
|---|---|---|---|
| f = O(g) | big-oh | f(n) ≤ c·g(n) for all n ≥ k | ≤ (upper bound) |
| f = Ω(g) | big-omega | f(n) ≥ c·g(n) for all n ≥ k | ≥ (lower bound) |
| f = Θ(g) | big-theta | both O(g) and Ω(g) | = (tight bound) |
| f = o(g) | little-oh | f grows strictly slower: f/g → 0 | < |
| f = ω(g) | little-omega | f grows strictly faster: f/g → ∞ | > |
How to prove f(n) = O(g(n))
The definition says: find constants c > 0 and k ≥ 1 with
The recipe for polynomials:
- For n ≥ 1, replace every smaller power of n by g(n) (it can only get bigger).
- Add the coefficients. That sum is c.
- The bound holds from n = 1, so k = 1.
Example 1. f(n) = 10n + 5. For n ≥ 1, 5 ≤ 5n, so 10n + 5 ≤ 15n. c = 15, k = 1 ⇒ O(n).
Example 2. f(n) = 3n² + 4n + 1. For n ≥ 1, 4n ≤ 4n² and 1 ≤ n², so f(n) ≤ 8n². c = 8, k = 1 ⇒ O(n²).
Simplifying rules
- Drop constant factors: O(5n) = O(n).
- Keep the dominant term: O(n² + n + 1) = O(n²).
- Sequential code adds: O(n) + O(n²) = O(n²).
- Nested code multiplies: a loop of n around a loop of n = O(n²).
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
- O(1)
- O(log n)
- O(n)
- O(n log n)
- O(n²)
- O(2ⁿ)
| O(1) | 1 |
|---|---|
| O(log n) | 4 |
| O(n) | 16 |
| O(n log n) | 64 |
| O(n²) | 256 |
| O(2ⁿ) | 65,536 |
Try the 10n+5 and 3n²+4n+1 presets, then your own coefficients.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main() {
cout << left << setw(6) << "n" << setw(9) << "log n" << setw(8) << "n"
<< setw(11) << "n log n" << setw(9) << "n^2" << "2^n\n";
for (int n : {1, 2, 4, 8, 16, 32}) {
double lg = log2(n);
cout << left << setw(6) << n << setw(9) << lg << setw(8) << n
<< setw(11) << n * lg << setw(9) << n * n << (long long)pow(2, n) << "\n";
}
// Big-O check for f(n) = 3n^2 + 4n + 1 with c = 8, k = 1
bool ok = true;
for (long long n = 1; n <= 1000; n++)
if (3 * n * n + 4 * n + 1 > 8 * n * n) ok = false;
cout << "3n^2+4n+1 <= 8n^2 for n = 1..1000: " << (ok ? "true" : "false") << "\n";
}n log n n n log n n^2 2^n 1 0 1 0 1 2 2 1 2 2 4 4 4 2 4 8 16 16 8 3 8 24 64 256 16 4 16 64 256 65536 32 5 32 160 1024 4294967296 3n^2+4n+1 <= 8n^2 for n = 1..1000: true
05Complexity
| O(1) | constant: array access, push/pop |
|---|---|
| O(log n) | logarithmic: binary search |
| O(n) | linear: linear search, traversal |
| O(n log n) | linearithmic: merge sort, heap sort |
| O(n²) | quadratic: bubble, selection, insertion sort |
| O(n³) | cubic: three nested loops |
| O(2ⁿ) | exponential: all subsets, naive Fibonacci |
Order to memorise: 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
06Watch
Asymptotic Notations: Big Oh, Omega, Theta
Why this one: The clearest explanation of O, Ω and Θ with the c and n₀ definition, exactly what proofs need.
Big O Notation
Why this one: Eight-minute intuition with code examples; good before tackling proofs.
07Exam lens
Likely questions
- Define Big-O, Big-Omega and Big-Theta formally.
- Show that f(n) = 10n + 5 is O(n). State your c and k.
- Show that f(n) = 3n² + 4n + 1 is O(n²).
- Arrange in increasing order of growth — n², log n, 2ⁿ, n, n log n, 1.
- What is the difference between O(g(n)) and o(g(n))?
Common mistakes
- Forgetting to state c and k explicitly. A proof without numbers gets partial marks.
- Claiming 3n² = O(n). False: no constant c makes 3n² ≤ c·n for all large n.
- Thinking Big-O means "worst case". Big-O is an upper bound on a function; you can give an upper bound for the best case too.
- Keeping constants or lower terms. O(2n² + n) should be written O(n²).
08Quick check
09Practice
🟢 Trace by hand
Prove that f(n) = 5n² + 3n + 2 is O(n²). Show c and k and check one value.
Show answer
For n ≥ 1: 3n ≤ 3n² and 2 ≤ 2n². So 5n² + 3n + 2 ≤ 5n² + 3n² + 2n² = 10n².
Choose c = 10, k = 1. Check n = 2: 20 + 6 + 2 = 28 ≤ 40 ✓. Therefore f(n) = O(n²). ∎
🟡 Implement it
Extend growth.cpp to check numerically, for n from 1 to 10 000, that 5n² + 3n + 2 ≤ 10n². Then try c = 5 and see where it fails.
Hint
With c = 5 it fails for every n ≥ 1, because 3n + 2 > 0. A numeric check doesn't replace a proof, but it does catch wrong constants.
🔴 Solve problems
Hint
Naive recursion is O(2ⁿ). A simple loop with two variables is O(n). Time both for n = 40.
Solution idea
int a = 0, b = 1; for (int i = 0; i < n; i++) { int c = a + b; a = b; b = c; } return a;Hint
Same recurrence as Fibonacci. Which growth rate does your solution have?
Hint
Dividing by 2 until you reach 1 is O(log n). There is also an O(1) bit trick
n > 0 && (n & (n-1)) == 0.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.