Big-Omega & Big-Theta: Best, Worst & Average Case

Algorithms & Complexity

Chapter 4 · Big-Omega & Big-Theta: Best, Worst & Average Case

Chapter 2 gave Big-O an upper bound and a promise: "Chapter 4's Big-Theta gives this convention a fully formal footing." Here it is — the other two asymptotic bounds, and a second, genuinely different axis this chapter untangles from them: best, worst, and average case.

Big-Omega — The Lower Bound

Big-Omega, formally

f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that f(n) ≥ c·g(n) for all n ≥ n₀.

Where Big-O says "grows no faster than," Big-Omega says "grows no slower than" — a floor under the growth, instead of a ceiling.

Big-Theta — The Tight Bound

Big-Theta, formally

f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)) — both bounds hold at once, pinning the growth rate down exactly.

This is the formal version of Chapter 2's own convention — "always report the tightest valid bound" really means: whenever possible, report the Θ class, since it's the one that's both an upper and lower bound simultaneously.

A Fully Worked Θ Proof

Reusing Chapter 2's own function, f(n) = 3n² + 5n + 100, already shown to be O(n²) with c=4, n₀=13:

Bound	Constants	Why it holds
O(n²)	c=4, n₀=13	Verified in Chapter 2 — `f(n) ≤ 4n²` for all `n ≥ 13`
Ω(n²)	c=3, n₀=1	`3n² + 5n + 100 ≥ 3n²` since `5n + 100` is always positive — trivially true for every `n ≥ 1`

Both bounds hold with real, verified constants — so f(n) = Θ(n²), not just informally "roughly n²." Interestingly, the lower bound here was the easier one to prove.

The Other Axis: Best, Worst & Average Case

Two genuinely different questions, easily conflated

O / Ω / Θ describe bounds on growth for a given scenario. Best/worst/average case describe which scenario — which specific input is being analyzed. They're orthogonal: an algorithm can have a Θ(1) best case and a completely separate Θ(n) worst case, both perfectly valid, tight bounds, just for different inputs.

Worked Example: Linear Search's Three Cases

Case	Scenario	Complexity
Best	Target is the very first element checked	Θ(1)
Worst	Target is the last element, or absent entirely	Θ(n)
Average	Target equally likely at any of the n positions	Θ(n)

For the average case, if the target sits at position k (1-indexed) with equal probability 1/n for each position, the expected number of comparisons is (1+2+...+n)/n = (n+1)/2 — verified directly at n=5: (1+2+3+4+5)/5 = 3, matching (5+1)/2 = 3 exactly.

n/2 is still Θ(n) — constants don't survive Big-notation

(n+1)/2 looks like "half the work" of the worst case, and in a literal sense it is — but Chapter 2's own dominant-term rule discards constant factors entirely. Both the worst case and the average case land in the exact same Θ(n) class; the factor-of-2 difference is real and worth knowing, but it's invisible to Big-notation by design.

Why Worst Case Matters Even When It's Rare

A security-adjacent real consequence

A hash table's average case lookup is famously Θ(1) — but its worst case, when many keys collide into the same bucket, degrades to Θ(n). This isn't just theoretical: an attacker who can predict or influence how a hash function distributes keys can deliberately craft input that forces every lookup into its worst case, turning a service's normally fast hash-table operations into a genuine denial-of-service vector. Average-case performance describes typical behavior; worst-case bounds describe what an adversary — or just unlucky data — can actually force.

Verifying Θ in Code

def f(n):
    return 3*n**2 + 5*n + 100

def is_Theta_n_squared(f, c_lower, c_upper, n0, test_range=range(1, 100)):
    return all(
        c_lower * n**2 <= f(n) <= c_upper * n**2
        for n in test_range if n >= n0
    )

print(is_Theta_n_squared(f, c_lower=3, c_upper=4, n0=13))  # True

def average_case_linear_search(n):
    return sum(range(1, n + 1)) / n

print(average_case_linear_search(5))  # 3.0 — matches (n+1)/2

Hands-On Exercises

Exercise 1

Inserting a new element into a sorted array (shifting elements to make room) has different complexities depending on where the new element belongs. State the best case (insert at the very end, no shifting needed) and worst case (insert at the very beginning, shifting every existing element) in Θ-notation, and explain why they differ.

📄 View solution

Exercise 2

Prove f(n) = 2n + 7 is Θ(n) by finding valid constants for both the O(n) bound and the Ω(n) bound, showing the smallest n₀ for which the O(n) bound (with c=3) first holds.

📄 View solution

Exercise 3

A colleague says "our hash table lookups are O(1), so performance is never a concern here." Using this chapter's own findings about best/worst/average case and the hash-collision example, explain what's missing from this claim.

📄 View solution

Chapter 4 Quick Reference

Big-Omega (Ω): lower bound — f(n) ≥ c·g(n) for constants c, n₀
Big-Theta (Θ): tight bound — both O and Ω hold simultaneously; the formal version of "report the tightest bound"
O/Ω/Θ (bound type) and best/worst/average case (which input scenario) are orthogonal — never conflate them
Linear search: Θ(1) best case, Θ(n) worst case, Θ(n) average case (even though average is only (n+1)/2 comparisons — constants vanish in Big-notation)
Worst-case bounds matter even when rare — they describe what an adversary or unlucky data can force, not just typical behavior (hash-collision DoS as a real example)
Next chapter: Recursive algorithms and recurrence relations