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 — which is why a Big-O answer never mentions seconds.

Two rules cover almost everything GATE asks: drop constant factors, and keep only the dominant term, meaning the one that grows fastest and so eventually dwarfs the rest.

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.

Here is the mix-up worth heading off early: “worst case” is not another way of saying “Big-O”. The two answer different questions.

Which input? — best, average, or worst — chooses the scenario you are describing. How fast does the work grow in that scenario? — O(n), O(n²) — describes the curve once the scenario is fixed.

So “linear search is O(1) in the best case” is an ordinary, correct sentence rather than a contradiction. When a question names no case, worst is the default; when it names one, answer for that one and say so.

• 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.

That is 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