Big-O: Best, Average & Worst Case

The last lesson left you counting a loop’s iterations exactly — and then asked the harder question: what happens when n is a million, and the exact count stops mattering? The answer is to stop counting steps and start classifying growth. Big-O answers one question: as the input grows, how does the work grow? It is a statement about the shape of the growth curve, not the raw speed of your machine. Two rules cover almost everything GATE asks — drop constant factors, and keep only the dominant (fastest-growing) term.

Growth rate, not raw count

Work of 3n^2 + 500n + 9000 is simply O(n^2) — push n high enough and the n^2 term buries the others, so the lower-order terms and the constant 3 are discarded. The same reasoning collapses O(2n) to O(n). You are classifying the curve, not counting exact operations.

These are the classes you must recognise, slowest-growing first:

Drag the slider up and watch O(2^n) explode past everything while O(n log n) barely moves — the chasm between these shapes is the reason algorithm choice matters more than any constant factor or faster CPU ever could.

Reading loop nests

Most GATE Big-O questions are answered by inspecting loops:

# (a) single loop — runs n times                       → O(n)
for i in range(n):
    work()

# (b) nested loops — n × n iterations                  → O(n^2)
for i in range(n):
    for j in range(n):
        work()

# (c) halving loop — n, n/2, n/4, ... down to 1        → O(log n)
i = n
while i > 1:
    i = i // 2
    work()

The halving loop (c) is the one beginners miss. Each step throws away half of what remains: 1024 → 512 → 256 → ... → 1. You can only halve n about log₂ n times — that count is the logarithm. Recognising “halve every step means logarithmic” in unfamiliar code is the real skill, not reciting the binary-search example.

Two recurrences worth memorising

When a function calls itself, its cost is a recurrence. Two show up constantly:

• T(n) = T(n/2) + O(1) → O(log n). One subproblem of half the size, constant work outside the call. This is binary search: each step does a single comparison, then recurses on one half.
• T(n) = 2T(n/2) + O(n) → O(n log n). Two half-size subproblems plus a linear merge. This is merge sort: log n levels of splitting, each level doing O(n) total work to combine.

You do not need the Master theorem here — recognising these two patterns by sight is enough for GATE DA.

Best vs average vs worst case

The same algorithm can have different complexities depending on the input. Worst case is the guarantee (the upper bound for any input); best case is the luckiest input; average case is the expectation over typical inputs.

• Linear search: best O(1) (target is first), worst O(n) (target is last or absent), average O(n).
• Quicksort: average O(n log n), but worst O(n^2) when pivots are consistently the smallest/largest element. This gap is GATE’s favourite “best vs worst” example.

To feel the halving count concretely, here is a loop that simply counts how many halvings it takes to drive n down to 1:

def halving_steps(n):
    steps = 0
    while n > 1:
        n = n // 2     # throw away half each step
        steps += 1
    return steps

print("steps for n=1024:", halving_steps(1024))
print("steps for n=64:  ", halving_steps(64))

prints:

steps for n=1024: 10
steps for n=64:   6

log₂ 1024 = 10 and log₂ 64 = 6 — the step count is the logarithm, which is why a halving loop is O(log n).

How GATE asks this

GATE DA asks Big-O as MCQs: classify a code snippet, or pick the complexity of a given recurrence. Sometimes it is a NAT — count the iterations of a halving loop or the steps of a recurrence for a specific n. The method never changes: read the loop structure (or match the recurrence), drop constants, keep the dominant term.

Worked classification

Three snippets, classified by inspection:

1. A single for i in range(n) → n iterations → O(n).
2. for i in range(n): for j in range(n) → n × n → O(n^2).
3. while n > 1: n = n // 2 → halves each step → O(log n).

For a sorted list of 1,000,000 items, binary search makes at most 20 comparisons, because log₂ 1,000,000 is about 20 — the whole point of logarithmic time, and a hint at why the next lesson cares so much about it.

A question to carry forward

One class keeps stealing the show: O(log n), the halving that shrinks a million items to twenty steps. And one algorithm keeps being named as its poster child — binary search. But naming it is not the same as understanding it. Here is the thread onward: how does binary search actually work, step by step — and what does it demand of the data before it can deliver that logarithmic magic, the demand that separates it from a plain linear scan?

In one breath

• Big-O = how work grows with n — the curve’s shape, not wall-clock time. Drop constants (O(2n)=O(n)), keep the dominant term (n²+n = O(n²)).
• Classes to know: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n).
• Read loops: single → O(n), nested → O(n²), halving → O(log n) (halve n about log₂ n times).
• Two recurrences: T(n)=T(n/2)+O(1) → O(log n) (binary search); T(n)=2T(n/2)+O(n) → O(n log n) (merge sort).
• Best ≠ worst: quicksort O(n log n) avg / O(n²) worst; linear search O(1) best / O(n) worst — always say which case.

Practice