Best, worst, average case — with examples: Question bank

Before you start, re-arm the three definitions:

Recall The three cases, in one breath

For a fixed size $n$ : best $B (n) = min_{∣ I ∣ = n} T (I)$ (least work over all size- $n$ inputs), worst $W (n) = max_{∣ I ∣ = n} T (I)$ (most work), average $A (n) = \sum_{I} Pr (I) T (I)$ (probability-weighted expected work). Only the input's arrangement/content varies — never $n$ .

True or false — justify

Answer each with T/F and one sentence of reasoning.

Worst case is always a larger input than best case.

False. Both are measured at the same

n

; you change the arrangement, not the size — worst case is the unluckiest layout of the same-sized input.

Best-case running time is the fastest an algorithm can ever run on any input at all.

False. It's the minimum over inputs of a fixed size $n$ , so it's still a function of

n

(e.g. insertion-sort best case is

Θ (n)

, not

Θ (1)

For linear search the average case equals exactly the midpoint of best and worst.

True, but only by luck:

\frac{1 + n}{2} = \frac{n + 1}{2}

because the cost is linear and uniform in position; this coincidence does not generalise (see quicksort).

If an algorithm's best and worst case are both

Θ (n)

, then its average case is also

Θ (n)

True. The average is a weighted mean squeezed between best and worst, so if both bounds are

Θ (n)

the average has no room to escape that order.

Big-O notation always refers to the worst case.

False.

O

Ω

Θ

are bound types (upper/lower/tight) and are independent of which case you analyse — you can write "best case is

O (n)

" perfectly well. See Asymptotic Notation.

Average case requires you to assume something about the inputs.

True.

A (n) = \sum_{I} Pr (I) T (I)

needs a probability distribution over inputs; change the assumed distribution and the average can change. See Expected Value.

Quicksort's average case is close to its worst case because both involve partitioning.

False. Average is

Θ (n lo g n)

and worst is

Θ (n^{2})

— an entire order apart — because catastrophically bad pivots are rare under random input. See Quicksort.

An algorithm with best case

Θ (1)

can never be considered "efficient" overall.

False. The best case being cheap says nothing about typical behaviour; you judge efficiency by the worst and average cases, not the lucky one.

The average case can be strictly larger than the worst case if inputs are weird enough.

False.

A (n)

is a weighted average of values that are all

\leq W (n)

, so it can never exceed the worst case; likewise it's never below the best case.

Spot the error

Each statement is wrong or muddled — name the mistake and fix it.

"Insertion sort is

Θ (n^{2})

, full stop."

The error is quoting one number for all cases; insertion sort is

Θ (n)

best (sorted) and

Θ (n^{2})

worst (reversed), so you must say which case

Θ (n^{2})

refers to. See Insertion Sort.

"Linear search worst case is when the array is very large."

Confuses size with arrangement; worst case is fixed-

n

and occurs when the key is last or absent (

n

comparisons), regardless of how big

n

is. See Linear Search.

"The average of best

Θ (1)

and worst

Θ (n)

Θ (n /2)

, which we simplify to

Θ (1)

Two errors: average is not the arithmetic midpoint, and

Θ (n /2) = Θ (n)

— constant factors vanish in

Θ

, so it would never simplify to

Θ (1)

"Worst case is pessimistic, so it always overstates real-world time badly."

It guarantees an upper bound, which is a feature not a flaw; for adversarial or safety-critical inputs the worst case is the realistic one, and it never understates time.

"Since quicksort's worst case is

Θ (n^{2})

, it's slower than merge sort in practice."

Conflates worst case with typical behaviour; quicksort's average

Θ (n lo g n)

with small constants makes it fast in practice, and randomised pivots make the

Θ (n^{2})

case vanishingly unlikely.

"Best case is useless information."

Not so — a large gap between best (

Θ (n)

) and worst (

Θ (n^{2})

), as in insertion sort, tells you the algorithm exploits structure (nearly-sorted data), which is genuinely useful.

"Amortized time is just the average case with a different name."

Different averaging: average case averages over the distribution of inputs, while amortized analysis averages the cost over a sequence of operations on one structure, with no probability involved.

Why questions

Answer with the actual reasoning, not a definition.

Why must all three cases hold

n

fixed?

If you let

n

vary you'd be comparing costs across different problem sizes, which mixes "growth with

n

" and "luck of arrangement" into one meaningless number.

Why does insertion sort's best case beat its worst by a whole order of growth?

On sorted input the inner while fails on its first test every time (1 comparison per element

\Rightarrow Θ (n)

), whereas reversed input forces each element to walk to the front (

\Rightarrow \sum i = Θ (n^{2})

Why can't the average case ever fall outside the best–worst range?

Every

T (I)

lies between

B (n)

and

W (n)

, and a probability-weighted mean of numbers in an interval stays inside that interval.

Why is the uniform-distribution assumption so common in average-case analysis?

It's the simplest, most symmetric model and often makes the sums tractable (e.g. Gauss's

\sum k = \frac{n ( n + 1 )}{2}

); but it's an assumption, and real inputs may follow a very different distribution.

Why does knowing the worst case matter even if it's rare?

For real-time, security, or hard-deadline systems you need a guarantee that holds even against an adversary who deliberately feeds you the worst input.

Why is "

O

= worst,

Ω

= best" a tempting but false shortcut?

Because worst case is usually stated with

O

and best with

Ω

in textbooks, but the bound type describes the shape of a bound (upper/lower/tight) and can be applied to any case independently.

Edge cases

Boundary and degenerate inputs — reason carefully.

Linear search on

n = 0

(empty array): what is each case?

All three collapse — the loop runs zero times and returns "not found" immediately, so best = worst = average

= Θ (1)

(a constant, the return itself).

Linear search when the key appears multiple times: does the worst case change?

No — the algorithm stops at the first match, so many matches can only make it faster; the worst case is still key-absent with

n

comparisons.

Insertion sort on

n = 1

: which case applies?

The outer loop for i in 1..n-1 never executes, so zero comparisons happen — a degenerate input where best, worst and average all equal

Θ (1)

Insertion sort on an array of all-equal elements: best or worst?

Best-like

Θ (n)

: since a[j] > key is never strictly true (equal is not greater), the inner loop stops immediately, just like the sorted case.

Average case when one input is astronomically more likely than the rest:

The average is dominated by that input's cost; a skewed distribution pulls

A (n)

toward the likely input, which is exactly why the assumed distribution must be stated.

Quicksort on an already-sorted array with a naive "first element" pivot:

This hits the worst case

Θ (n^{2})

, because each pivot splits off just one element — sorted input is the trap that motivates randomised pivots. See Quicksort.

What if best case = worst case for some algorithm?

Then the running time is input-insensitive at each

n

(e.g. summing every element of an array is always

Θ (n)

), and the average is forced to the same order — no spread at all.

Connections

Parent: Best, Worst, Average Case — the concepts these traps probe.
Asymptotic Notation (Big-O, Omega, Theta) — why bound-type ≠ case.
Linear Search · Insertion Sort · Quicksort — the algorithms the edge cases use.
Expected Value and Probability Distributions — the distribution assumption behind average case.
Amortized Analysis — the other kind of averaging, contrasted above.