Big-O: Best, Average & Worst Case

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 makes O(2n) collapse 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 gap between these shapes is the reason algorithm choice matters.

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.

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.

Quick check