Big-O, Big-Θ, Big-Ω — and Best/Average/Worst · Data Structures & Algorithms Quest

"Two different questions get mixed up constantly: 'how tight is my bound?' and 'which input am I analyzing?' They're separate axes. Untangling them clears up half the confusion."

Axis One: How Tight Is the Bound?

O, Θ, and Ω are three ways to bound one function's growth:

Big-O is an upper bound: "grows at most this fast." Saying an algorithm is O(n²) promises it's never worse than quadratic — but it might be better.
Big-Ω (Omega) is a lower bound: "grows at least this fast." It's the floor.
Big-Θ (Theta) is a tight bound: upper and lower agree, so it's the true shape. Θ(n) means "grows exactly like n, no loophole."

In casual conversation, people say "O(n)" when they really mean Θ(n) — the exact shape. That's usually fine; just know that strictly, O is only the ceiling. When someone pedantically corrects your "O" to "Θ," this is what they're on about.

Axis Two: Which Input?

This is a completely different axis, and conflating it with the first is the classic beginner mix-up. Best / average / worst case asks: for a given input size, which arrangement of the input am I looking at?

Best case — the luckiest input. Linear search finds it at position 0: O(1). Rarely the number you should care about.
Worst case — the unluckiest input. Linear search scans everything and misses: O(n). This is usually the number that matters, because it's the guarantee.
Average case — the typical input, averaged over realistic data. Linear search: about n/2 → still O(n).

So quicksort is "Θ(n log n) average, Θ(n²) worst" — two different inputs, two different shapes, both true. Hash lookup is "O(1) average, O(n) worst." You're not contradicting yourself; you're naming different inputs.

O/Θ/Ω bound a single function's growth (ceiling / exact / floor). Best/average/worst pick which input you analyze. Different axes — don't fuse them. Design for the worst case; expect the average.

Which Number Should Rule Your Decisions?

Usually two: the worst case (the promise you can keep no matter what the user throws at you) and the average case (what actually happens most of the time). Best case is mostly bragging — "it's O(1) if the answer happens to be first" tells you nothing useful. When a system needs hard guarantees (real-time, safety-critical), worst case is king; when it just needs to be fast in practice, average case often wins the design.

Pippa's Confession

I once shipped something on its average-case O(1) and forgot the worst case was O(n). Then a user fed it exactly the pathological input — every key colliding — and "instant" became "frozen." Average case is what you hope for; worst case is what you're accountable for. Now I always ask Dad's follow-up myself: "and what's the worst an adversary could do to this?"

Code

Best, worst, average — same code·python

# One algorithm, three inputs: best, worst, average case.

def linear_search(items, target):
    """Returns (found, comparisons)."""
    for i, x in enumerate(items):
        if x == target:
            return True, i + 1        # comparisons used
    return False, len(items)

data = list(range(1000))

# BEST case: target is first -> 1 comparison -> O(1)
print("best :", linear_search(data, 0)[1])

# WORST case: target absent -> scan all -> O(n)
print("worst:", linear_search(data, -1)[1])

# AVERAGE case: target somewhere in the middle -> ~n/2 -> still O(n)
print("avg  :", linear_search(data, 500)[1])

# Same code, same n. The INPUT chooses best/worst/average.
# Big-O of the worst case here is O(n); best case is O(1).

Exercise

For each, name the best, worst, and average case complexity: (1) checking if a list contains a value with a linear scan, (2) inserting at the front of a Python list, (3) finding a key in a hash map. Then say which case you'd design around for a system that must never freeze.

Hint

Front-insert into a list is always O(n) (every case the same — it shifts everything). Hash lookup is O(1) average but O(n) worst — and a never-freeze system must respect that worst case.

Big-O, Big-Θ, Big-Ω — and Best/Average/Worst

Axis One: How Tight Is the Bound?

Axis Two: Which Input?

Which Number Should Rule Your Decisions?

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0