What does O(n²) - quadratic complexity - mean?

AlgorithmsJunior~3 min read

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)

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)
}

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;
}

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;
}

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

Use hash structures (Map/Set) to check membership or find a pair in O(1) on average.
Sort and apply two pointers or binary search: usually O(n log n) instead of O(n²).
Cache/memoize subproblem results so the same thing isn't recomputed.
Early stopping and pruning cases where further enumeration is pointless.
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.

Short Answer

Interview ready

Premium

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