Suggest an edit

Improve this article

Refine the answer for “What does "worst case" mean (worst case)?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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

1. Linear search over an array: worst O(n) (the element is at the end or absent), best O(1), average O(n).
2. Binary search in a sorted array: worst O(log n), since the depth of the halvings is logarithmic.
3. 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).
4. A hash table: average lookup O(1), but worst O(n) with numerous collisions (for example, malicious keys).
5. 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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts831 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.