Suggest an edit

Improve this article

Refine the answer for “What does asymptotic complexity 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)

## Short answer

Asymptotic complexity is a way to estimate how an algorithm's costs (in time and memory) grow as the size of the input data n increases. We describe growth with functions and compare them by order, dropping constants and lower-order terms. The notations O (upper bound), Θ (tight bound), and Ω (lower bound) are used for this.

- What is measured: running time and/or memory consumption as a function of n.
- Why: to compare algorithms by scalability, rather than by specific milliseconds.
- How to read it: O(n log n) grows slower than O(n²), and O(1) is constant.

## Detailed explanation

Asymptotic complexity describes an algorithm's behavior for large n, that is, "in the limit". Instead of absolute measurements, we count how many basic operations execute and how that number grows as n increases. This lets us compare algorithms independently of the language, hardware, and compiler/engine optimizations.

### Notations

- O(g(n)) - an upper bound: "no worse than g(n) for large n". Example: quicksort is O(n log n) on average, O(n²) in the worst case - so asymptotically it is no worse than quadratic in the worst case.
- Θ(g(n)) - a tight asymptotic bound: bounded both above and below by the same function g(n). Example: summing an array is Θ(n).
- Ω(g(n)) - a lower bound: "no better than g(n)". Example: comparisons in a comparison-based sort are Ω(n log n).

### Why we drop constants and lower-order terms

Constants and lower orders do not affect scalability. An algorithm with 1000·n is faster than one with 0.001·n² only up to a certain threshold; for large n, the quadratic one inevitably loses to the linear one. That is why O(n) is preferable to O(n²), even if the O(n) implementation is slower on small inputs.

### Typical complexity classes and intuition

- O(1): constant - accessing an array element by index, a hash insert/lookup (on average).
- O(log n): logarithmic - binary search, operations on balanced trees.
- O(n): linear - a single pass over the data (filter/map/reduce).
- O(n log n): quasi-linear - efficient comparison sorts (quicksort/merge sort), many "divide and conquer" algorithms.
- O(n²): quadratic - two nested passes (naive duplicate search, bubble sort).
- O(2^n), O(n!): exponential/factorial - a full enumeration of subsets/permutations.

### Code examples (JavaScript)

```javascript
// O(1): indexed access and push (amortized)
const arr = [10, 20, 30];
const x = arr[1]; // O(1)
arr.push(40);      // amortized O(1)

// O(n): linear search
function linearSearch(a, target) {
  for (let i = 0; i < a.length; i++) {
    if (a[i] === target) return i; // best case: O(1), worst case: O(n)
  }
  return -1;
}

// O(log n): binary search (the array must be sorted)
function binarySearch(a, target) {
  let l = 0, r = a.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1;
    if (a[m] === target) return m;
    if (a[m] < target) l = m + 1; else r = m - 1;
  }
  return -1; // worst case: O(log n)
}

// O(n log n): sorting (typical average estimate)
const sorted = [...arr].sort((a, b) => a - b); // average: O(n log n)

// O(n^2): nested loops
function hasDuplicatesQuadratic(a) {
  for (let i = 0; i < a.length; i++) {
    for (let j = i + 1; j < a.length; j++) {
      if (a[i] === a[j]) return true;
    }
  }
  return false; // worst case: O(n^2)
}

// Optimized to O(n) time and O(n) memory using a set
function hasDuplicatesLinear(a) {
  const seen = new Set();
  for (const v of a) {
    if (seen.has(v)) return true;
    seen.add(v);
  }
  return false; // time: O(n), memory: O(n)
}
```

### Best, average, and worst case

- Linear search: best O(1) (first element), average O(n), worst O(n).
- Binary search: best O(1), worst O(log n).
- Quicksort: average O(n log n), worst O(n²) without randomization/a good pivot choice.

### Amortized complexity

Sometimes a single operation is expensive, but on average over a series of operations it is cheap. Example: a dynamic array doubles its buffer and copies elements when it runs out of space (a rare O(n) operation). However, most pushes are O(1), so the average cost of one push over a long series is amortized O(1).

### Memory (space complexity)

In addition to time, extra memory is assessed. For example, merge sort uses O(n) extra memory, quicksort uses O(log n) of recursion stack (on average), and a linear pass with a Set uses O(n) memory to store unique elements.

### How to answer in an interview

- Define n: the input size (number of elements, vertices, edges, string length).
- Describe which operations dominate and how many times they run (an iteration counter, recurrence relations).
- Give estimates for time and memory: best/average/worst, and amortized if needed.
- Justify the simplifications: why constants and lower-order terms were dropped, which growth factor dominates.

### A short checklist

1. Name the input parameter n.
2. Identify the dominant operations and their count.
3. Write down the estimate: O, Θ, Ω (time and memory).
4. Note the best/average/worst or amortized cases.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.