Worst-case running time

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

The worst-case running time $T(n)$ is the maximum time taken by an algorithm on any input of size $n$.

◇Key Concepts

Formal expression: $T(n) = \max\{T(I) : |I| = n\}$ Why it is the default performance metric Connection to ◇Big-O Notation and ◇Worst-Case Analysis Distinguished from average-case and best-case running time

◇Details / Theory

Definition

The worst-case running time is the function:
$T(n) = \max_{\text{all inputs } I \text{ of size } n} T(I)$

It represents the longest possible execution time for any input of a given size. This is the standard metric used in ◇Algorithm Analysis.

Why It Is the Default Metric

1. Guarantee: Gives an upper bound on execution time — the algorithm will never take longer.
2. No probability assumptions: Unlike ◇Average-Case Analysis, no distribution over inputs is needed.
3. Simplicity: Typically easier to analyze than average-case.
4. Safety: Critical for real-time and safety-critical applications.

Expressing Worst-Case Running Time

Usually expressed using ◇Big-O Notation: e.g., $T(n) = O(n^2)$. For a tight bound, ◇Big-Theta Notation is preferred: $T(n) = \Theta(n^2)$. The actual function may be something like $T(n) = 3n^2 + 5n + 2$, but we care about the ◇Order of Growth.

Examples

[!tip] Key Insight
Merge Sort has the same worst-case and best-case running time ($\Theta(n \log n)$), while Quick Sort’s worst-case ($n^2$) is much worse than its average-case ($n \log n$).

◇Common Pitfalls

Assuming all algorithms have different best/worst/average cases — some (like Merge Sort) are the same across all cases. Confusing the worst-case running time of an algorithm with the lower bound of a problem.

◇Summary

TL;DR — Worst-case running time is the maximum time an algorithm takes on any input of size $n$. It’s the default analysis metric because it provides guaranteed performance bounds.

◇Links

Related: ◇Worst-Case Analysis — ◇Running Time — ◇Time Complexity — ◇Big-O Notation — ◇Average-Case Analysis — ◇Best-Case Analysis Source / Reference: Handout 01, Page 3

◇References & Navigation

• Previous Topic: ◇Worst-Case Analysis
• Next Topic: ◇Reccurences
• Related Notes: ◇Worst-Case Analysis, ◇Running Time