Best, Average & Worst Case

Jr Codex DSA Notes

Level: Beginner Prerequisites: Chapter 4 Time to complete: ~15 minutes

Why One Algorithm Has Multiple Complexities
Worked Example: Linear Search
Worked Example: Quick Sort
Which Case Should You Care About?
Notation Note: Big O, Big Ω, Big Θ
Summary & Next Steps

1. Why One Algorithm Has Multiple Complexities

The same algorithm can behave very differently depending on the arrangement of the input, not just its size. Three scenarios are usually distinguished:

Best case — the most favorable input (fewest operations needed).
Average case — expected performance across typical/random inputs.
Worst case — the least favorable input (most operations needed).

In interviews and in practice, worst case is the default assumption unless stated otherwise — it's the guarantee you can actually rely on.

2. Worked Example: Linear Search

def linear_search(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1

Case	Scenario	Complexity
Best	`target` is the first element	`O(1)`
Average	`target` is somewhere in the middle (or found after scanning half, on average)	`O(n)`
Worst	`target` is the last element, or not present at all	`O(n)`

3. Worked Example: Quick Sort

Quick sort (implemented in Module 3) is the clearest illustration of why this distinction matters:

Case	Scenario	Complexity
Best	Pivot always splits the data into two roughly equal halves	`O(n log n)`
Average	Pivot splits reasonably well most of the time (random input)	`O(n log n)`
Worst	Pivot is always the smallest or largest element (e.g., already-sorted input with a naive pivot choice)	`O(n²)`

This is why quick sort's implementation details — how the pivot is chosen — matter in practice: a poor pivot strategy turns an O(n log n) algorithm into an O(n²) one on inputs that are common in the real world (like nearly-sorted data).

4. Which Case Should You Care About?

Default to worst case when comparing algorithms or stating complexity — it's the only case that gives you a hard guarantee, which matters for systems that must stay responsive under any input.
Average case matters when worst-case inputs are rare in practice, and you care more about typical throughput (e.g., hash map operations, covered in Module 8, are O(1) average but O(n) worst case).
Best case is rarely the headline number, but it's still worth knowing — it explains why an algorithm might feel fast during casual testing before it hits a pathological input.

5. Notation Note: Big O, Big Ω, Big Θ

You'll sometimes see this trio in more formal treatments:

Big O (O)      — upper bound: "no worse than this"     → used for worst case
Big Omega (Ω)  — lower bound: "no better than this"     → used for best case
Big Theta (Θ)  — tight bound: "exactly this," both bounds meet

This curriculum uses Big O throughout, following the industry-standard convention of describing worst-case behavior, since that's what interviews and most engineering docs expect.

6. Summary & Next Steps

Key Takeaways

The same algorithm can have different best/average/worst-case complexities depending on input arrangement, not just size.
Worst case is the default and most cited number — it's the only guarantee that holds for any input.
Quick sort is the canonical example: O(n log n) average/best, but O(n²) worst case with a poor pivot strategy.
Big Ω and Big Θ formalize best-case and tight bounds respectively, but this curriculum follows convention and uses Big O (worst case) by default.

Concept Check

Why is worst case the default assumption when no other case is specified?
What input causes quick sort's worst case, and why?
When would average-case complexity be more relevant than worst-case?

Next Chapter

→ Chapter 6: Practice — Analyzing Complexity of Code Snippets

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index