Complexity Analysis: Best Case, Worst Case, and Average Case

Algorithm analysis classifies performance by how an algorithm behaves on inputs of the same size but different arrangements. The three standard viewpoints are best-case complexity, worst-case complexity, and average-case complexity.2

For an input size $n$:

• Best case measures the minimum number of operations required by any valid input of size $n$.2
• Worst case measures the maximum number of operations required by any valid input of size $n$.2
• Average case measures the expected number of operations, which depends on a clearly stated input distribution or set of allowable inputs.2

A key point is that these are different functions of the same algorithm, not different algorithms. For some algorithms, the three cases are close; for others, they differ substantially.2

A compact comparison is shown below.

A useful way to visualize the idea is:

3

Footnotes

1. Best, worst and average case - Wikipedia - Definitions of best, worst, and average case, including why worst-case guarantees matter in practice. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. 19.2 Average-Case Running Time of Linear Search - Course notes explaining that average-case analysis depends on the chosen input set and probability model. ↩ ↩² ↩³

3. Worst, Average and Best Case Analysis of Algorithms - GeeksforGeeks - Introductory explanation of the three cases with algorithmic examples such as linear search. ↩ ↩² ↩³

4. Best, Worst, and Average Cases — OpenDSA - Educational discussion of when worst-case or average-case analysis is appropriate, especially in real-time systems. ↩ ↩²

To differentiate the three cases precisely, consider the running-time function $T(I)$ for an input instance $I$ of size $n$.

If $\mathcal{I}_n$ denotes the set of all inputs of size $n$, then:

$$T_{\text{best}}(n) = \min_{I \in \mathcal{I}_n} T(I)$$ $$T_{\text{worst}}(n) = \max_{I \in \mathcal{I}_n} T(I)$$

For average case, if each input $I \in \mathcal{I}_n$ has probability $P(I)$, then:

$$T_{\text{avg}}(n) = \sum_{I \in \mathcal{I}_n} P(I)\,T(I)$$

This formula shows why expected value is central in average-case analysis: without a probability model, “average” is undefined or ambiguous.2

Suitable examples

1. Linear search

   • Best case: target is the first element, so only one comparison is needed, giving $\Theta(1)$.2
   • Worst case: target is absent or appears last, so all $n$ elements are checked, giving $\Theta(n)$.3
   • Average case: if the target is equally likely to be at any position, the expected number of comparisons is about $\frac{n+1}{2}$, so $\Theta(n)$.

2. Insertion into a sorted array

   • Best case: the new item belongs at the end, so little shifting is needed.
   • Worst case: it belongs at the beginning, so many elements must shift.
   • Average case: expected shifting depends on where insertion positions tend to occur.

3. Quicksort

   • Best case: partitions split evenly, leading to $\Theta(n \log n)$.
   • Worst case: partitions are extremely unbalanced, leading to $\Theta(n^2)$.
   • Average case: under common probabilistic assumptions, expected time is $\Theta(n \log n)$.

These examples illustrate that case analysis is not merely symbolic notation; it reflects how input structure affects computation.3

Footnotes

1. 19.2 Average-Case Running Time of Linear Search - Course notes explaining that average-case analysis depends on the chosen input set and probability model. ↩

2. Best, Worst, and Average Cases — OpenDSA - Educational discussion of when worst-case or average-case analysis is appropriate, especially in real-time systems. ↩ ↩²

3. Best, worst and average case - Wikipedia - Definitions of best, worst, and average case, including why worst-case guarantees matter in practice. ↩ ↩² ↩³

4. Linear search - Wikipedia - Analysis of linear search including best case, worst case, and expected comparisons under standard assumptions. ↩ ↩² ↩³

5. Worst, Average and Best Case Analysis of Algorithms - GeeksforGeeks - Introductory explanation of the three cases with algorithmic examples such as linear search. ↩

6. Lecture #2 Worst-Case Analysis vs. Average Case Analysis - Duke University - Notes contrasting worst-case and average-case behavior using quicksort and mergesort. ↩ ↩² ↩³ ↩⁴

Linear search as the canonical demonstration

Linear search is the clearest example for comparing best, worst, and average cases because its behavior depends directly on the target's position.

Suppose we search for value $x$ in an array of length $n$:

If the array is:

$$[4, 9, 12, 18, 25]$$

and we search for $4$, the algorithm stops immediately after one comparison. This is the best case, so:

$$T_{\text{best}}(n) = \Theta(1)$$

If we search for $25$, or for a missing value like $30$, the algorithm checks every element. This is the worst case, so:

$$T_{\text{worst}}(n) = \Theta(n)$$

If each position is equally likely to contain the target once, then the expected number of comparisons is:

$$\frac{1 + 2 + 3 + \cdots + n}{n} = \frac{n+1}{2}$$

Hence:

$$T_{\text{avg}}(n) = \Theta(n)$$

This is a powerful teaching example because the best case is constant, while both average and worst case grow linearly.2

2

Footnotes

1. Linear search - Wikipedia - Analysis of linear search including best case, worst case, and expected comparisons under standard assumptions. ↩ ↩² ↩³

2. 19.2 Average-Case Running Time of Linear Search - Course notes explaining that average-case analysis depends on the chosen input set and probability model. ↩ ↩²

Why worst-case analysis is often preferred in practice

Although all three perspectives are valuable, worst-case analysis is often preferred for practical and engineering reasons.2

1. It gives a guaranteed upper bound

Worst-case analysis tells us that the algorithm will never do worse than this bound for any input of size $n$.2 This makes it suitable when reliability matters more than optimism.

2. It does not require uncertain probability assumptions

Average-case analysis depends on knowing how inputs are distributed.2 In many real systems, that distribution is unknown, changes over time, or is adversarial. Worst-case analysis avoids this modeling problem.

3. It is crucial in real-time and safety-critical systems

In systems such as monitoring, control, and scheduling, missing a deadline may be unacceptable. Educational materials on algorithm analysis explicitly note that real-time applications often require worst-case guarantees rather than “good performance most of the time.”2

4. It supports robust design

A worst-case bound helps compare algorithms conservatively. If Algorithm A is better than Algorithm B even in the worst case, that comparison is strong and distribution-independent.2

5. It guards against pathological inputs

Some algorithms perform well on most inputs but degrade sharply on specially structured ones. Worst-case analysis reveals this risk. Quicksort is the standard example: despite excellent average behavior, its classical worst case is $\Theta(n^2)$.

At the same time, worst-case analysis can be pessimistic. That is why practice sometimes combines it with average-case, amortized, randomized, or smoothed analysis.2 Still, as a first guarantee, worst-case remains the default in many textbooks, proofs, and system specifications.3

Footnotes

1. Best, worst and average case - Wikipedia - Definitions of best, worst, and average case, including why worst-case guarantees matter in practice. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Best, Worst, and Average Cases — OpenDSA - Educational discussion of when worst-case or average-case analysis is appropriate, especially in real-time systems. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. 19.2 Average-Case Running Time of Linear Search - Course notes explaining that average-case analysis depends on the chosen input set and probability model. ↩

4. Worst, Average and Best Case Analysis of Algorithms - GeeksforGeeks - Introductory explanation of the three cases with algorithmic examples such as linear search. ↩ ↩²

5. Lecture #2 Worst-Case Analysis vs. Average Case Analysis - Duke University - Notes contrasting worst-case and average-case behavior using quicksort and mergesort. ↩ ↩² ↩³

Direct answer to the prompt

(i) Differentiation

• Best-case complexity is the minimum running time for inputs of size $n$; it reflects the most favorable input arrangement.2
• Worst-case complexity is the maximum running time for inputs of size $n$; it provides an upper bound and a performance guarantee.3
• Average-case complexity is the expected running time over inputs of size $n$ under an explicitly stated probability model.2

(ii) Demonstration using linear search

For an array of length $n$:

• If the target is the first element, only one comparison is made: best case = $\Theta(1)$.2
• If the target is absent or last, all $n$ elements are checked: worst case = $\Theta(n)$.2
• If the target is equally likely to be in any position, the expected comparisons are $\frac{n+1}{2}$: average case = $\Theta(n)$.

(iii) Why worst-case analysis is often preferred

Worst-case analysis is preferred because it gives guaranteed bounds, does not rely on fragile assumptions about input probabilities, and is essential when systems must meet deadlines or remain correct under all circumstances.2 It is therefore the most conservative and dependable basis for algorithm selection in many practical settings.3

Footnotes

1. Best, worst and average case - Wikipedia - Definitions of best, worst, and average case, including why worst-case guarantees matter in practice. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. Worst, Average and Best Case Analysis of Algorithms - GeeksforGeeks - Introductory explanation of the three cases with algorithmic examples such as linear search. ↩ ↩² ↩³

3. Best, Worst, and Average Cases — OpenDSA - Educational discussion of when worst-case or average-case analysis is appropriate, especially in real-time systems. ↩ ↩² ↩³ ↩⁴

4. 19.2 Average-Case Running Time of Linear Search - Course notes explaining that average-case analysis depends on the chosen input set and probability model. ↩

5. Linear search - Wikipedia - Analysis of linear search including best case, worst case, and expected comparisons under standard assumptions. ↩ ↩² ↩³