Algorithms and complexity: Big O without fear

// We count steps — the number of comparisons — not milliseconds
const range = (n) => Array.from({ length: n }, (_, i) => i);

// O(n): in the worst case we look at every element
function linearSteps(list, target) {
  let steps = 0;
  for (const value of list) {
    steps++;
    if (value === target) break;
  }
  return steps;
}

// O(n²): every element is compared with every element
function pairSteps(n) {
  let steps = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) steps++;
  }
  return steps;
}

// O(log n): each step discards half of the sorted array
function binarySteps(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;
  let steps = 0;
  while (low <= high) {
    steps++;
    const middle = Math.floor((low + high) / 2);
    if (sorted[middle] === target) break;
    if (sorted[middle] < target) low = middle + 1;
    else high = middle - 1;
  }
  return steps;
}

const sizes = [10, 1000, 100000];
console.log(sizes.map((n) => linearSteps(range(n), -1))); // [ 10, 1000, 100000 ]
console.log(sizes.map((n) => binarySteps(range(n), -1))); // [ 3, 9, 16 ]
console.log(sizes.slice(0, 2).map((n) => pairSteps(n))); // [ 100, 1000000 ]

/**
 * Binary search in an array sorted in ascending order.
 * Returns the index of the element found or -1. Complexity: O(log n).
 */
export function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;

  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    const value = sorted[middle];

    if (value === target) return middle;
    if (value < target) low = middle + 1; // the target is to the right of the middle
    else high = middle - 1; // the target is to the left of the middle
  }

  return -1;
}

import { test } from "node:test";
import assert from "node:assert/strict";
import { binarySearch } from "./binary-search.mjs";

const prices = [490, 900, 1200, 1500, 2300, 4100, 7800];

test("finds the first, middle and last element", () => {
  assert.equal(binarySearch(prices, 490), 0);
  assert.equal(binarySearch(prices, 1500), 3);
  assert.equal(binarySearch(prices, 7800), 6);
});

test("returns -1 when the element is missing", () => {
  assert.equal(binarySearch(prices, 100), -1); // smaller than all
  assert.equal(binarySearch(prices, 1000), -1); // between neighbours
  assert.equal(binarySearch(prices, 9999), -1); // larger than all
});

test("empty array and single-element array", () => {
  assert.equal(binarySearch([], 5), -1);
  assert.equal(binarySearch([5], 5), 0);
  assert.equal(binarySearch([5], 7), -1);
});

test("matches indexOf on arrays of different lengths", () => {
  for (let n = 0; n <= 64; n++) {
    const evens = Array.from({ length: n }, (_, i) => i * 2); // 0, 2, 4, …
    for (let target = -1; target <= n * 2; target++) {
      assert.equal(binarySearch(evens, target), evens.indexOf(target), `n=${n}, target=${target}`);
    }
  }
});

// 1. Without a compare function, elements are compared as strings
console.log([25, 100, 3].toSorted()); // [ 100, 25, 3 ]
console.log([25, 100, 3].toSorted((a, b) => a - b)); // [ 3, 25, 100 ]

// 2. Strings by UTF-16 code units: "é" lands after "z"
const words = ["zebra", "éclair", "apple"];
console.log(words.toSorted()); // [ 'apple', 'zebra', 'éclair' ]
console.log(words.toSorted((a, b) => a.localeCompare(b, "en"))); // [ 'apple', 'éclair', 'zebra' ]

// 3. Stability (ES2019+): equal elements keep their original order
const orders = [
  { id: 1, status: "new" },
  { id: 2, status: "paid" },
  { id: 3, status: "new" },
  { id: 4, status: "paid" },
];
const byStatus = orders.toSorted((a, b) => a.status.localeCompare(b.status));
console.log(byStatus.map((order) => order.id)); // [ 1, 3, 2, 4 ]

// 4. How many times the comparator runs is a V8 implementation detail, not a spec guarantee
function countComparisons(list) {
  let calls = 0;
  list.toSorted((a, b) => {
    calls++;
    return a - b;
  });
  return calls;
}
let seed = 1;
const random = () => (seed = (seed * 48271) % 2147483647); // reproducible "random" numbers
const shuffled = Array.from({ length: 1000 }, random);
const alreadySorted = shuffled.toSorted((a, b) => a - b);
console.log(countComparisons(alreadySorted)); // 999
console.log(countComparisons(shuffled)); // 8630

const orders = Array.from({ length: 50000 }, (_, i) => ({ id: 100000 + i, total: (i % 90) * 100 }));
const requested = [100007, 149999, 123456, 999999];

// No index: every request is a find over the whole array, O(n) per request
let scanned = 0;
const viaFind = requested.map((id) =>
  orders.find((order) => {
    scanned++;
    return order.id === id;
  }),
);
console.log(scanned); // 123465 — elements scanned for 4 requests

// With an index: one O(n) pass to build it, then get is on average faster than O(n)
const byId = new Map(orders.map((order) => [order.id, order]));
const viaMap = requested.map((id) => byId.get(id));
console.log(byId.size); // 50000 — the index takes memory
console.log(viaMap.map((order) => order?.total)); // [ 700, 4900, 5600, undefined ]
console.log(viaFind.every((order, i) => order === viaMap[i])); // true

// 100,000 order numbers; every thousandth one repeats an earlier number
const ids = Array.from({ length: 100_000 }, (_, i) => (i % 1000 === 999 ? i - 500 : i));

// O(n²): indexOf inside filter — a nested loop, just hidden
function duplicatesNaive(list) {
  return list.filter((value, index) => list.indexOf(value) !== index);
}

// O(n): a single pass with a Set check
function duplicatesWithSet(list) {
  const seen = new Set();
  const duplicates = [];
  for (const value of list) {
    if (seen.has(value)) duplicates.push(value);
    else seen.add(value);
  }
  return duplicates;
}

function measure(label, fn) {
  const start = performance.now();
  const result = fn(ids);
  console.log(`${label}: ${(performance.now() - start).toFixed(1)} ms`);
  return result;
}

const naive = measure("filter + indexOf", duplicatesNaive);
const fast = measure("Set", duplicatesWithSet);
console.log(naive.length, fast.length); // 100 100
console.log(naive.every((value, i) => value === fast[i])); // true

$ node duplicates.mjs
filter + indexOf: 7438.3 ms
Set: 24.1 ms
100 100
true