Big-O, Big-Ω & Big-Θ Notation Explained — Best, Average & Worst Case

Three Runners, Three Roads

Every time you write a loop, call a sort function, or query a database, you're implicitly choosing a road for your data to travel. The notations below give you a precise, mathematical language to describe that journey — and to compare it with any alternative.

The Three Notations

Each notation answers a different question about your algorithm's performance. Used together they give you a complete picture of how it behaves across all possible inputs.

Asymptotic Notation — The Formal Theory

Θ-Notation — Asymptotically Tight Bound

Θ is the central notation in CLRS. It is a two-sided bound: f(n) is squeezed between two constant multiples of g(n) once n is large enough. Formally, Θ(g(n)) is a set of functions:

O-Notation & Ω-Notation — The One-Sided Bounds

Drop one side of the sandwich and you get the one-sided bounds. O keeps only the ceiling; Ω keeps only the floor.

A Worked Proof — ½n² − 3n = Θ(n²)

This is the canonical CLRS example. To prove a Θ bound we must produce actual constants c₁, c₂ and a threshold n₀ that satisfy the definition. We need: c₁n² ≤ ½n² − 3n ≤ c₂n² for all n ≥ n₀.

little-o and little-ω — The Strict (Non-Tight) Bounds

O and Ω allow the bound to be tight (f can equal a constant multiple of g). The lowercase cousins forbid that: they describe bounds that are strictly looser, the way < differs from ≤.

The Real-Number Analogy

Cormen draws a memorable parallel: comparing the growth rates of two functions is like comparing two real numbers a and b. This single table makes all five notations click.

Formal Properties of Asymptotic Notation

These properties (CLRS §3.1) let you manipulate bounds algebraically. Note which ones each notation obeys — the gaps are as instructive as the entries.

Growth Curves — Animated Diagram

Watch how each complexity class explodes (or barely grows) as input size n increases from 1 to 20. The vertical axis represents relative time units. Even at small n, the difference between O(n²) and O(n log n) is dramatic.

Common Data Structure Operations

The table below shows how the three complexity cases map to real operations across the most common data structures. Use it as a quick reference when choosing a structure for a specific access pattern.

Real-World Impact: O(n²) vs O(n log n)

Abstract notation becomes concrete when you count actual steps. Sorting 1,000 items with bubble sort versus merge sort reveals a gap that grows catastrophically with scale.

Python Code — Annotated Examples

Linear Search — O(n) worst, O(1) best

def linear_search(arr, target):
    # Best case: target is first element → O(1)
    # Average case: target is in the middle → O(n/2) = O(n)
    # Worst case: target is last or absent → O(n)
    for i, val in enumerate(arr):
        if val == target:
            return i      # Found — stops early in best/average case
    return -1            # Not found — always scans every element

nums = [4, 7, 2, 9, 1, 5, 8, 3, 6]
print(linear_search(nums, 4))   # Best case: found at index 0 → 1 step
print(linear_search(nums, 6))   # Worst case: found at index 8 → 9 steps
print(linear_search(nums, 99))  # Miss: scans all 9 elements → 9 steps

Binary Search — O(log n) worst, O(1) best

def binary_search(arr, target):
    # REQUIRES: arr must be sorted
    # Best case: target is the middle element → O(1)
    # Worst case: target is absent or at the edges → O(log n)
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2   # Integer division — halves the search space
        if arr[mid] == target:
            return mid              # Found
        elif arr[mid] < target:
            left = mid + 1          # Discard left half
        else:
            right = mid - 1         # Discard right half

    return -1                       # Target not found

sorted_nums = [1, 3, 5, 7, 9, 11, 13, 15, 17]
# n = 9 → log₂(9) ≈ 3.17 → at most 4 iterations
print(binary_search(sorted_nums, 9))   # Best: hits middle (index 4) instantly
print(binary_search(sorted_nums, 1))   # Worst: 4 iterations to reach left edge
print(binary_search(sorted_nums, 99))  # Miss: 4 iterations, exhausts range

Bubble Sort — O(n²)

def bubble_sort(arr):
    # O(n²) — two nested loops, each up to n iterations
    # Best case O(n) with early exit when already sorted
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):   # Each pass bubbles largest to end
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break                         # Early exit: already sorted
    return arr

data = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(data))  # ~21 comparisons for n=7

Merge Sort — O(n log n)

def merge_sort(arr):
    # O(n log n) — divides in half log n times, merges in O(n) each time
    # Θ(n log n): same complexity for ALL inputs — no lucky case
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])   # Recurse left half
    right = merge_sort(arr[mid:])   # Recurse right half

    return _merge(left, right)

def _merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

data = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(data))  # ~17 comparisons for n=7 vs bubble's ~21

The Complexity Ladder

These classes form a hierarchy from constant time bliss to exponential despair. Each rung of the ladder tells you what a million-item input actually means in practice.

When Each Notation Matters

Knowing the notations is half the job. Knowing when to reach for each is what separates a practitioner from someone who's just memorised definitions.

The Golden Rules

These seven rules cover the most common mistakes in complexity analysis. Internalise them and your Big-O derivations will rarely be wrong.