15 Algorithm Analysis, Big-O, Omega, and Theta
16 Algorithm Analysis: Big-O, Omega, and Theta
Week 7, Session 1. CSS 342.
16.1 Warmup
Two programs sort the same list of 10⁶ integers. Program A is O(n²). Program B is O(n log n). Estimate the wall-clock difference, given a CPU that does roughly 10⁹ simple operations per second.
- A: 10¹² operations ≈ 1000 seconds (~17 minutes).
- B: ~2 × 10⁷ operations ≈ 0.02 seconds.
Factor of ~50,000. That gap is why we care about asymptotic analysis.
16.2 Learning objectives
- State the formal definitions of O, Ω, and Θ and use them to classify a function.
- Derive the time complexity of a given loop structure (single, nested, halving).
- Classify the STL container operations from chapters 2–3 by complexity.
- Distinguish best, average, and worst case with concrete examples.
- Drop constants and lower-order terms correctly when expressing asymptotic complexity.
16.3 Why asymptotic notation
Real running time depends on hardware, compiler, input size, cache state, a tangle of variables. Big-O strips it down to “how does the running time grow as the input grows?”
If your function does roughly 100n + 50 operations, big-O says O(n). The 100 and the 50 vanish. If it does n² + 10n, big-O says O(n²) and the 10n is lower-order. The notation captures the shape, not the constants.
The reason I redesigned CSS 342 and 343 around LeetCode-style problems is exactly this. Students were graduating with strong theory and no instinct for what a quadratic loop felt like at scale. Now the warmups are practice for the interview, and the analysis is the language we use to talk about why one solution is better than another. It is the same content. The framing makes it stick.
16.4 Formal definitions
Big-O (upper bound): f(n) is O(g(n)) if there exist constants c > 0 and n₀ such that for all n ≥ n₀, f(n) ≤ c · g(n).
In words: “f grows no faster than g, ignoring constants and small inputs.”
Big-Omega (lower bound): f(n) is Ω(g(n)) if there exist constants c > 0 and n₀ such that for all n ≥ n₀, f(n) ≥ c · g(n).
Big-Theta (tight bound): f(n) is Θ(g(n)) if f(n) is both O(g(n)) and Ω(g(n)).
In day-to-day conversation people say “O(n)” when they mean “Θ(n).” Technically you can say merge sort is O(n²), it is also O(n¹⁰⁰), but those are useless upper bounds. We almost always want the tight bound, which is Θ. The CS culture nonetheless says “big-O” everywhere. I will use “O” loosely meaning “Θ” except when the distinction matters.
16.5 The classes you must memorize
| Class | Name | Example |
|---|---|---|
| O(1) | constant | array indexing, unordered_map::count (avg) |
| O(log n) | logarithmic | binary search, set::find |
| O(n) | linear | one pass through a vector |
| O(n log n) | linearithmic | merge sort, std::sort |
| O(n²) | quadratic | nested loops over the same array |
| O(2ⁿ) | exponential | naive recursive Fibonacci, brute-force subsets |
| O(n!) | factorial | brute-force permutations, naive 8-queens |
Memorize the order. For n = 10⁶: O(1) is instant; O(log n) is 20 operations; O(n) is a million; O(n log n) is 20 million; O(n²) is a trillion (already too slow); O(2ⁿ) is much worse than the age of the universe.
16.6 Analyzing loops
16.6.1 Single loop
for (int i = 0; i < n; ++i) {
// O(1) work
}Total work: n × O(1) = O(n).
16.6.2 Nested loop
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// O(1) work
}
}n × n × O(1) = O(n²).
16.6.3 Triangular loop
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
// O(1) work
}
}Sum: n + (n-1) + … + 1 = n(n+1)/2 = O(n²).
16.6.4 Halving loop
while (n > 1) {
n /= 2;
}n becomes n/2, n/4, n/8, …, 1. After log₂(n) iterations, the loop stops. O(log n).
16.6.5 Doubling loop
for (int i = 1; i < n; i *= 2) {
// O(1) work
}i becomes 1, 2, 4, 8, …, n. Same count: log₂(n). O(log n).
16.7 STL complexity cheat sheet
| Operation | vector |
set |
unordered_set |
map |
unordered_map |
priority_queue |
|---|---|---|---|---|---|---|
| insert | O(1) amortized (push_back) | O(log n) | O(1) avg | O(log n) | O(1) avg | O(log n) |
| find | O(n) | O(log n) | O(1) avg | O(log n) | O(1) avg | n/a |
| erase | O(n) | O(log n) | O(1) avg | O(log n) | O(1) avg | n/a |
| top/front | O(1) | O(log n) (begin) | O(1) | O(log n) | O(1) | O(1) |
“Amortized O(1)” for push_back means: usually O(1), occasionally O(n) when the vector grows. Averaged over many insertions, O(1).
16.8 Best, average, worst case
Linear search:
- Best: target is at index 0. O(1).
- Worst: target is at the end (or not present). O(n).
- Average (assuming uniform): n/2. O(n).
Binary search:
- Best: target is the first midpoint. O(1).
- Worst: target is at a leaf of the search tree. O(log n).
- Average: O(log n).
Quicksort:
- Best: pivot always perfectly bisects. O(n log n).
- Average: O(n log n).
- Worst: pivot is always extreme. O(n²).
Quicksort’s worst case is one of the reasons std::sort uses introsort, quicksort that falls back to heapsort when recursion is too deep.
16.9 Dropping constants and lower-order terms
3n² + 100n + 5 → O(n²)
2^(n+10) → O(2ⁿ)
n log n + n → O(n log n)
log(n²) → O(log n) // because log(n²) = 2 log nLast one trips people up. log(n²) = 2 log n, so it is the same big-O as log n. Constants do not change the class.
16.10 Try it
Analyze the time complexity of:
for (int i = 1; i <= n; i *= 2) {
for (int j = 0; j < n; ++j) {
// O(1)
}
}Outer loop: O(log n). Inner: O(n). Total: O(n log n).
16.11 Self-check
std::unordered_map::find on average?5n³ + 2ⁿ + 1000:16.12 Challenges
- Time
std::sortvs. a hand-written bubble sort on n = 1,000, 10,000, 100,000. Plot. Confirm O(n log n) vs. O(n²). - Compute the operation count for a halving loop with a counter. Match against
⌈log₂ n⌉. - Write a function and analyze its complexity formally, identify dominant term, drop lower order, drop constants.
16.13 Where this fits
Big-O lets us talk about algorithms before we run them. The next chapter applies it to sorting algorithms, the bread and butter of complexity analysis.
| You are here | Coming up |
|---|---|
| O / Ω / Θ definitions, loop analysis, STL complexity | Chapter 14: sorting algorithms |