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

  1. State the formal definitions of O, Ω, and Θ and use them to classify a function.
  2. Derive the time complexity of a given loop structure (single, nested, halving).
  3. Classify the STL container operations from chapters 2–3 by complexity.
  4. Distinguish best, average, and worst case with concrete examples.
  5. 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. 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²) — the 10n is lower-order. The notation captures the shape, not the constants.

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 n

Last 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

1. What is the complexity of std::unordered_map::find on average?
b. Hash-table lookup is O(1) average, O(n) worst (when collisions degenerate).
2. Simplify 5n³ + 2ⁿ + 1000:
c. Exponential dominates polynomial for large n. Drop the rest.

16.12 Challenges

  1. Time std::sort vs. a hand-written bubble sort on n = 1,000, 10,000, 100,000. Plot. Confirm O(n log n) vs. O(n²).
  2. Compute the operation count for a halving loop with a counter. Match against ⌈log₂ n⌉.
  3. 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