Best, Worst, and Average Case — Understanding Algorithm Bounds

Three Types of Analysis

For any algorithm, the runtime can vary depending on the specific input. We describe this with three measures:

Best Case (Ω)

The minimum number of operations for any input of size n. Example: insertion sort on an already-sorted array is O(n) — it just makes one pass.

Worst Case (O)

The maximum number of operations for any input of size n. This is the most commonly used measure because it provides a guarantee. Example: quicksort degrades to O(n²) when the pivot is always the smallest or largest element.

Average Case (Θ)

The expected number of operations averaged over all possible inputs (or a probability distribution over inputs). Example: quicksort’s average-case is O(n log n) assuming random pivot selection.

Comparison Table

Algorithm	Best	Average	Worst
Insertion sort	O(n)	O(n²)	O(n²)
Quick sort	O(n log n)	O(n log n)	O(n²)
Merge sort	O(n log n)	O(n log n)	O(n log n)
Hash lookup	O(1)	O(1)	O(n)
Binary search	O(1)	O(log n)	O(log n)

Which Case Should You Use?

• Worst case for safety-critical systems, real-time systems, and when you need guarantees.
• Average case for general-purpose software where inputs are reasonably random.
• Best case is rarely useful on its own but helps understand an algorithm’s adaptive behavior.

Big-O vs Big-Ω vs Big-Θ

• Big-O (O): upper bound — “at most this fast”
• Big-Ω (Ω): lower bound — “at least this slow”
• Big-Θ (Θ): tight bound — “exactly this growth rate”

When people say “merge sort is O(n log n),” they usually mean Θ(n log n) — it’s both the upper and lower bound.