Suggest an edit

Improve this article

Refine the answer for “What does "worst case" mean?”. 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?

### Short answer

The worst case is an estimate of the upper bound on resources (time and/or memory) that an algorithm or operation may require for the most unfavorable input data. It is usually expressed in O(·) notation and guarantees that, for any input, the complexity will not exceed the stated bound.

- Answers the question: "How bad can it get?"
- Gives a guarantee: time/memory will not be worse than the stated estimate.
- Contrasts with the "average" and "best" cases.

### Detailed answer

Algorithm analysis considers three scenarios: the best, average, and worst cases. The worst case is the input scenario in which the algorithm runs the longest or consumes the most memory. This estimate matters because it gives an upper bound on complexity, that is, a strict guarantee: "it won't be worse than this."

1. Best case: minimal cost. Example - searching for an element that is in the first position: O(1).
2. Average case: averaging over the distribution of inputs. Example - searching for a random element in an unsorted array: ≈O(n/2) → O(n).
3. Worst case: maximal cost. Example - searching for an element that is not in the array: O(n).

#### Why this matters in an interview

- It shows you can reason about guaranteed time/memory bounds, not just "average" performance.
- It lets you compare data structures and algorithms under peak load (API latency, traffic growth, adversarial inputs).
- It helps explain a choice: "Why does a hash table fit here rather than a balanced tree?" - accounting for the worst-case complexity.

#### Typical examples of a "worst case"

1. Linear search in an unsorted array: O(n) - if the element is absent (you scan the whole array).
2. Quicksort: O(n^2) - if the worst pivot is chosen every time (for example, an already sorted array with a poor pivot choice).
3. Hash table lookup: O(n) - with many collisions (all keys landing in one bucket).
4. Backtracking regular expressions: an exponential blow-up in time on certain strings (catastrophic backtracking) - important when filtering user input.

#### Relation to space complexity

The worst case applies to memory too: for example, recursion depth on an unfavorable input can require O(n) of stack, whereas on average it needs less. In memory-constrained systems (a mobile browser, no unlimited storage) this is critical.

#### How to reason about the worst case

- Define the operation you treat as the primitive: comparison, indexed access, insertion, and so on.
- Find the input data that forces the maximum number of such operations (for example, a missing element, sorted input for a poor pivot, and so on).
- Estimate the asymptotics in terms of n (input size) and/or other parameters (number of keys, depth, graph width).

#### Code example: linear search and its worst case

In an unsorted array, linear search in the worst case must scan every element: O(n). The best case is when the element is found in the first position: O(1). The average case is roughly half a pass: O(n).

```js
// Linear search: returns the index or -1 if not found
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // found - early exit
  }
  return -1; // worst case - scanned the whole array and found nothing
}

// Demonstration: best, average, and worst cases
const arr = Array.from({ length: 100000 }, (_, i) => i); // [0, 1, 2, ...]

console.time('best');
linearSearch(arr, 0); // best case: element at the start → O(1)
console.timeEnd('best');

console.time('average');
linearSearch(arr, Math.floor(arr.length / 2)); // average case → ≈O(n)
console.timeEnd('average');

console.time('worst');
linearSearch(arr, -1); // worst case: element absent → O(n)
console.timeEnd('worst');
```

#### Practical interview tips

- First state that you are estimating the upper bound: "In the worst case, time is O(n) and memory is O(1)."
- Briefly compare with an alternative (for example, a hash table versus an array) and explain what changes in the worst case.
- State your assumptions: input distribution, whether preprocessing (sorting) is possible, memory/latency constraints.
- If adversarial inputs are possible (user input, attacks), rely on worst-case guarantees.

#### A short checklist for the interview answer

- Give the definition: the upper bound on time/memory for the worst input.
- Name the asymptotics: O(·) for time and for memory.
- Compare with the best/average cases in one sentence.
- Give a mini example (search, sorting) and explain why it is the worst input.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.