Suggest an edit

Improve this article

Refine the answer for “What does O(n²) - quadratic 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

O(n²) is quadratic time complexity: an algorithm's running time grows proportionally to the square of the input size n. A typical source is nested loops over the same dataset, giving roughly n × n elementary operations.

## Detailed answer

### Definition and essence

Writing O(n²) means that the number of elementary operations an algorithm performs for an input of size n can be bounded above by an expression of the form c·n² + a·n + b, where the constants c, a, b do not depend on n. In O-notation only the dominant (fastest-growing) term is considered - n² - while constants and lower-order terms are dropped.

> Intuitively: if you double n, the time roughly grows 4x; if you increase n 10x, it roughly grows 100x.

### When O(n²) arises

- Two nested loops over the same array/list.
- Enumerating all pairs of elements in a set (the number of pairs is n(n-1)/2).
- Some sorts in the worst case (for example, bubble sort, selection sort, insertion sort - worst case).
- Operations on n×n matrices where every element must be visited (for example, comparing every row against every row).

### Code examples (JavaScript)

1) Counting the number of pairs - a classic O(n²):

```javascript
function countPairs(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      count++; // elementary operation
    }
  }
  return count; // ~ n(n-1)/2 => O(n^2)
}
```

2) Bubble sort - worst case O(n²), best case O(n) thanks to an early exit:

```javascript
function bubbleSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // the array is already sorted => a linear pass
  }
  return a;
}
```

3) Comparing O(n²) with an improved version: the Two Sum problem (finding a pair with a given sum).

```javascript
// Naive: O(n^2)
function twoSumBrute(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return null;
}

// Efficient with a Map: O(n) time, O(n) memory
function twoSumHash(nums, target) {
  const map = new Map(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) return [map.get(need), i];
    map.set(nums[i], i);
  }
  return null;
}
```

4) Different loop sizes: O(n·m). If m is proportional to n, this degenerates into O(n²):

```javascript
function processGrid(n, m) {
  let ops = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      ops++;
    }
  }
  return ops; // O(n*m); if m ≈ n, then O(n^2)
}
```

### Counting operations and intuition

A triangular enumeration is common: i runs from 0 to n-1, j runs from i+1 to n-1. Then the number of iterations equals 1 + 2 + ... + (n-1) = n(n-1)/2, which asymptotically leads to O(n²). This explains why comparing "everyone with everyone" quickly becomes expensive.

### How this feels in practice

| n | Operations ~ n² | Growth vs n=1 |
|---|---|---|
| 10 | 100 | ×100 |
| 100 | 10,000 | ×10,000 |
| 1,000 | 1,000,000 | ×1,000,000 |

### When O(n²) is acceptable

- Small n (tens or hundreds), a one-off run, no hard SLOs.
- Prototyping, where development speed matters more than ideal asymptotics.

### How to improve from O(n²) to something faster

1. Use hash structures (Map/Set) to check membership or find a pair in O(1) on average.
2. Sort and apply two pointers or binary search: usually O(n log n) instead of O(n²).
3. Cache/memoize subproblem results so the same thing isn't recomputed.
4. Early stopping and pruning cases where further enumeration is pointless.
5. Reformulate the problem (math/geometry/data structures) so you don't have to compare "everyone with everyone."

### Important nuances for an interview

- O(n²) is an upper bound. If you want to emphasize the "exact" asymptotics, use Θ(n²).
- Nested loops do not always mean O(n²): if the inner loop runs a constant number of times in total, the complexity can be O(n).
- O(n·m) is not the same as O(n²). But if m ≈ n, it becomes quadratic.
- Memory: O(n²) time does not imply O(n²) memory. Storing all pairs is already O(n²) memory; standalone nested loops may use only O(1) memory.

### Summary

O(n²) is the classic signature of algorithms that enumerate all pairs of elements. It quickly becomes impractical as n grows, so in interviews you are expected to either justify why quadratic complexity is acceptable for the given n, or propose a strategy to bring it down to O(n log n) or O(n) using sorting, hash structures, and other techniques.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.