TypeScript Quadratic Time O(n²)

A Loop Inside a Loop

O(n²) means quadratic time: the work grows with the square of the input. Twice the elements, four times the steps. Ten times the elements, a hundred times the steps.

The tell-tale shape in code is a loop inside a loop, both running over the same data. The outer loop runs n times, and for each of those the inner loop runs n times again: n · n steps.

Quadratic is fine for small arrays. For 100,000 elements it is already 10 billion steps — that is where programs start to hang.

All Pairs

The most direct O(n²) task: combine every element with every element. 4 letters make 4 · 4 = 16 pairs; 100 letters would make 10,000.

Build every pair

The outer loop picks x, the inner loop pairs it with every y. 4 elements produce 16 pairs — the square of the input size.

Write a TypeScript program with the string array a, b, c, d that uses two nested loops to print every pair of letters (like aa ab ac ad) on one line per outer element, counting the pairs. At the end print how many elements made how many pairs.

> Output: TypeScript file and captured output

Prompt

Write a TypeScript program with the string array a, b, c, d that uses two nested loops to print every pair of letters (like aa ab ac ad) on one line per outer element, counting the pairs. At the end print how many elements made how many pairs.

Output: TypeScript file and captured output

const letters = ["a", "b", "c", "d"]
let pairs = 0

for (const x of letters) {
  const row: string[] = []
  for (const y of letters) {
    row.push(x + y)
    pairs++
  }
  console.log(row.join(" "))
}

console.log(letters.length, "elements made", pairs, "pairs")

Bubble Sort

Bubble sort is the classic quadratic algorithm: it repeatedly walks the array and swaps neighbours that are in the wrong order. Big values "bubble" to the end, one pass at a time.

With its two nested loops it makes about n²/2 comparisons. It is a great algorithm to learn from — and a bad one to use: nums.sort((a, b) => a - b) does the same job in O(n log n).

Sort with two nested loops

Sorting 5 elements takes 4 + 3 + 2 + 1 = 10 comparisons. For 1,000 elements it would be about half a million — while an O(n log n) sort needs about ten thousand.

Write a TypeScript program that sorts the number array 5, 3, 8, 1, 4 with bubble sort — two nested loops that swap neighbours in the wrong order — while counting the comparisons. Print the sorted array and the number of comparisons.

> Output: TypeScript file and captured output

Prompt

Write a TypeScript program that sorts the number array 5, 3, 8, 1, 4 with bubble sort — two nested loops that swap neighbours in the wrong order — while counting the comparisons. Print the sorted array and the number of comparisons.

Output: TypeScript file and captured output

const nums = [5, 3, 8, 1, 4]
let comparisons = 0

for (let i = 0; i < nums.length - 1; i++) {
  for (let j = 0; j < nums.length - 1 - i; j++) {
    comparisons++
    if (nums[j] > nums[j + 1]) {
      const left = nums[j]
      nums[j] = nums[j + 1]
      nums[j + 1] = left
    }
  }
}

console.log("sorted:", nums)
console.log("comparisons:", comparisons)

Duplicates the Slow Way

Checking every element against every element that comes after it is another nested-loop pattern — comparing all pairs to find a duplicate.

It works, but it is O(n²). The Space Complexity page in this group shows the standard trick that makes this linear: remember the values you have already seen in a Map.

Find a duplicate with two loops

Each element is compared with every later element. The duplicate pair of 1s is found after 7 checks; in the worst case — no duplicate at all — all 15 pair checks run.

Write a TypeScript program that finds a duplicate value in the number array 3, 1, 4, 1, 5, 9 by comparing every element with every later element in two nested loops, counting the checks. When a duplicate is found, print the value and the number of checks so far.

> Output: TypeScript file and captured output

Prompt

Write a TypeScript program that finds a duplicate value in the number array 3, 1, 4, 1, 5, 9 by comparing every element with every later element in two nested loops, counting the checks. When a duplicate is found, print the value and the number of checks so far.

Output: TypeScript file and captured output

const nums = [3, 1, 4, 1, 5, 9]
let checks = 0

for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    checks++
    if (nums[i] === nums[j]) {
      console.log("duplicate:", nums[i], "after", checks, "checks")
    }
  }
}