What does "worst case" mean (worst case)?

AlgorithmsJunior~3 min read

What does "worst case" mean (worst case)?

Short answer

The worst case is an estimate of the maximum time and/or memory cost of an algorithm for any input data of a given size n. It is an upper bound (Big-O) that guarantees nothing will be worse than this, even on the most unfavorable data set.

Detailed explanation

When we analyze an algorithm, we are interested in how many resources it might require. The "worst case" answers the question: what is the maximum running time or memory an algorithm will need if it encounters the most unfavorable input of size n. Such an estimate is usually written using Big-O (for example, O(n), O(n log n), O(n²)) and serves as a strict guarantee from above.

Why this matters

Performance guarantees: shows the upper bound and helps you meet an SLA.
Assessing scalability: how the algorithm behaves as n grows.
Comparing alternatives: choosing between algorithms and data structures.
Safety and resilience: understanding worst-case scenarios helps avoid degradation in production.

Best, Average, Worst, Amortized

Best case: the minimum cost on a "lucky" input.
Average case: the mathematical expectation of the cost over all inputs (or some distribution).
Worst case: the maximum cost over all inputs of size n (an upper bound).
Amortized complexity: the average cost of an operation over a long sequence of operations (for example, push on a dynamic array is amortized O(1), even though an individual resizing operation is more expensive).

Examples for different algorithms

Linear search over an array: worst O(n) (the element is at the end or absent), best O(1), average O(n).
Binary search in a sorted array: worst O(log n), since the depth of the halvings is logarithmic.
Quicksort: average O(n log n), but worst O(n²) if the pivot is chosen poorly (for example, the first element on an already sorted array).
A hash table: average lookup O(1), but worst O(n) with numerous collisions (for example, malicious keys).
A balanced search tree (AVL/Red-Black): search/insert/delete are worst O(log n) thanks to balancing.

Code example: worst case for linear search

// O(n) in the worst case: the element is absent or is at the very end
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // early exit - best/average case
  }
  return -1; // walked the entire array - worst case
}

const data = Array.from({ length: 100000 }, (_, i) => i); // [0..99999]
console.time('worst');
linearSearch(data, -1); // absent: worst-case scenario
console.timeEnd('worst');

Code example: worst case for quicksort

// Simple quicksort that picks the first element as the pivot
// On a sorted array, this choice gives a recursion depth of n and O(n^2)
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = [];
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

const sorted = Array.from({ length: 20000 }, (_, i) => i);
console.time('qs-worst');
quickSort(sorted); // worst case for this pivot choice
console.timeEnd('qs-worst');

How to reason about the worst case in an interview

Define the problem size: what is n (array length, number of nodes, number of requests)?
Find the algorithm's branches and the "unfavorable" inputs that maximize the work.
Assess nested loops, recursion, and the dominant operations (comparisons, moves, API calls).
Write down the final upper bound in Big-O and, if needed, state the memory (space complexity).
If relevant, mention mitigations (randomization, balancing, limits) that soften worst-case scenarios.

A short formulation for an interview answer

The worst case is the upper bound on an algorithm's complexity: the maximum time and/or memory cost for any input of size n. It shows how slowly the algorithm can run in the most unfavorable scenario and gives performance guarantees.

Contexts in web development

DOM manipulation: traversing/modifying a large number of nodes is often O(n), where n is the number of elements.
Parsing JSON/CSV: parsing time grows with the size of the input - O(n).
Regular expressions: unfortunate patterns can cause catastrophic backtracking, up to an exponential worst case.
SQL/N+1 queries: the worst case is a full table scan or a cascade of hundreds of queries, giving O(n²) in the number of entities.
Network queues/retries: aggressive retries without backoff can multiply the time in the worst case.

Typical pitfalls

Confusing the average case with the amortized complexity.
Ignoring the model of the input data: in the worst case, what matters is the "worst" input, not a typical one.
Forgetting about memory: sometimes the time is acceptable, but memory becomes the bottleneck in the worst case.
Focusing only on Big-O without constants: algorithms that are theoretically identical can differ a lot in practice.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.