Start learning free

TYPESCRIPT · BIG O NOTATION

Time Complexity Practice 3 in TypeScript, explained

What quadratic time means

An algorithm runs in quadratic time, written O(n²), when the work grows with the square of the input size. Double the input and the work becomes four times larger; triple it and the work grows ninefold. For an array with a million elements, that is the difference between a million steps and a trillion.

The most common source is a loop nested inside another loop, where both depend on n:

function countPairs(arr: number[]): number {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] + arr[j] === 10) {
        count++;
      }
    }
  }
  return count;
}

The outer loop runs n times. Each time, the inner loop runs n times. The innermost line therefore executes n * n times. Counting it for n = 10, 20, 40 gives 100, 400 and 1600: each doubling of n multiplies the count by four.

Counting the work

To find the complexity, multiply the iterations of nested loops: an outer loop of n iterations and an inner loop of n iterations give n * n. Statements that sit in the outer loop but outside the inner one run only n times and don't change the answer.

Two loops placed one after the other are different: they add. A loop of n steps followed by another loop of n steps is n + n = 2n, which is O(n). Only nesting multiplies.

The inner loop doesn't have to start at zero

A very common pattern compares each element with the ones after it, so no pair is checked twice:

function hasDuplicate(arr: number[]): boolean {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        return true;
      }
    }
  }
  return false;
}
console.log(hasDuplicate([3, 1, 4, 1]));
console.log(hasDuplicate([3, 1, 4]));
true
false

The inner loop runs n - 1 times for i = 0, n - 2 times for i = 1, and so on down to zero. The total is (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2. For n = 10, 20, 40 the inner body runs 45, 190 and 780 times, exactly the formula. Big O drops constant factors and lower-order terms, and n(n - 1) / 2 is n²/2 - n/2, so it is still O(n²). Half as many steps does not change how the cost grows.

Loops hidden inside method calls

A quadratic algorithm is not always written with two visible loops. Many array methods loop internally. includes, indexOf, slice and concat are all O(n) in the worst case, so calling one inside a loop over n elements gives O(n²):

function common(a: number[], b: number[]): number[] {
  const out: number[] = [];
  for (const x of a) {
    if (b.includes(x)) {
      out.push(x);
    }
  }
  return out;
}
console.log(common([1, 2, 3, 4], [3, 4, 5]));
[ 3, 4 ]

If a and b both have about n elements, the loop runs n times and each includes may scan all of b, so the total is O(n²). Keeping the elements of b in a Set first lets each check use has, which takes O(1) on average, and the function becomes O(n).

The same idea speeds up duplicate detection:

function hasDuplicate(arr: number[]): boolean {
  const seen = new Set<number>();
  for (const x of arr) {
    if (seen.has(x)) {
      return true;
    }
    seen.add(x);
  }
  return false;
}

This version makes a single pass, at the price of O(n) extra space for the set. Trading memory for speed like this is a recurring theme in the chapters ahead.

When quadratic is acceptable

For small inputs, O(n²) is fine and often the simplest code. With n = 1,000 it is about a million steps, which a computer handles in a blink. With n = 100,000 it is ten billion steps, which is far too slow. When a problem gives large limits, quadratic time is a signal to look for a better idea: sorting, a set or map, or two pointers.

Simple sorting algorithms such as bubble sort and insertion sort are quadratic as well, while the sorting built into the language is faster than that.

Common mistakes

  • Thinking n(n - 1) / 2 is better than O(n²). It is half the steps, but the growth rate is the same.
  • Adding nested loops instead of multiplying them, or multiplying sequential ones.
  • Calling includes, indexOf or slice inside a loop and counting it as one step.
  • Assuming an early return helps the worst case. hasDuplicate can stop early on the first match, but when the array has no duplicates every pair is checked.

Key takeaways

  • Nested loops that both run about n times give O(n²); doubling the input quadruples the work.
  • Comparing every pair of elements takes n(n - 1) / 2 comparisons, which is still O(n²).
  • Look for hidden loops in methods like includes and slice.
  • A Set or Map often reduces a quadratic search to linear time.
Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free