Big-O and Complexity Analysis

Big-O notation answers one question: as the input gets bigger, how much more work does the algorithm do? It ignores constants and hardware — it is about the shape of growth, not the exact millisecond count.

The growth-rate table

The same table from the intro, extended with concrete step counts. Watch what happens to each row as n grows:

Notation	n = 10	n = 1,000	n = 1,000,000
O(1)	1	1	1
O(log n)	3	10	20
O(n)	10	1,000	1,000,000
O(n log n)	33	10,000	20,000,000
O(n^2)	100	1,000,000	10^12
O(2^n)	1,024	10^301	never finishes

Two takeaways:

• For small inputs, everything is fast. Complexity only matters as n grows — which is exactly why slow code passes tests and dies in production.
• O(log n) barely grows at all. Doubling a million-element input adds one step to a binary search. This is why sorted data and trees are so valuable.

Each class, with JavaScript

O(1) — constant

The work does not depend on input size:

function firstItem(arr) {
  return arr[0];
}

const roles = new Map([["rizwan", "admin"], ["hafsa", "editor"]]);
roles.get("hafsa");

Array index access, Map.get, Set.has, push, pop — all constant time.

O(log n) — logarithmic

Each step cuts the remaining work in half. Binary search is the canonical example:

function binarySearch(sorted, target) {
  let lo = 0;
  let hi = sorted.length - 1;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

A million elements take at most 20 iterations, because 2 to the power 20 is about a million.

O(n) — linear

One pass over the input. Twice the data, twice the work:

function maxValue(nums) {
  let max = -Infinity;
  for (const n of nums) {
    if (n > max) max = n;
  }
  return max;
}

Most single loops, includes, indexOf, filter, map, and reduce are linear.

O(n log n) — log-linear

The cost of good comparison sorting. Merge sort does log n levels of splitting, each level doing O(n) merging work. Array.prototype.sort lives here:

const scores = [82, 41, 95, 67];
scores.sort((a, b) => a - b);

O(n^2) — quadratic

Nested loops over the same input. Fine for hundreds of items, deadly for millions:

function hasDuplicate(arr) {
  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;
}

A Set does the same job in O(n):

function hasDuplicateFast(arr) {
  return new Set(arr).size !== arr.length;
}

Spotting an accidental O(n^2) — often disguised as includes or indexOf inside a loop — and replacing it with a hash-based O(n) solution is the single most common optimization in interviews and in real code.

O(2^n) — exponential

Every element doubles the work, typically because you try every combination:

function allSubsets(arr) {
  if (arr.length === 0) return [[]];
  const [first, ...rest] = arr;
  const without = allSubsets(rest);
  const withFirst = without.map((s) => [first, ...s]);
  return [...without, ...withFirst];
}

console.log(allSubsets([1, 2, 3]).length); // 8

Sometimes exponential is genuinely required — there really are 2^n subsets. The skill is recognizing when a problem does not require it and a dynamic-programming or greedy approach exists.

Rules for deriving complexity

1. Sequential steps add. A loop followed by another loop is O(n) + O(n), which simplifies to O(n).
2. Nested steps multiply. A loop inside a loop over the same input is O(n * n) = O(n^2). A loop of n over a loop of m is O(n * m).
3. Drop constants. O(3n) is O(n). Big-O cares about growth shape, not multipliers.
4. Drop lower-order terms. O(n^2 + n) is O(n^2) — for large n, the smaller term is noise.
5. Count hidden loops. arr.includes(x) looks like one line but is an O(n) scan. Built-ins have costs; know them (covered per-method in Arrays, Strings and Hash Maps).
6. State the variable. "It is O(n)" means nothing until you say what n is: elements, characters, nodes, edges. Graph algorithms are usually stated as O(V + E) — vertices plus edges.

Space complexity

The same notation applied to extra memory instead of time:

function countOccurrences(words) {
  const counts = new Map();
  for (const w of words) {
    counts.set(w, (counts.get(w) || 0) + 1);
  }
  return counts;
}

Time is O(n); space is also O(n) in the worst case, because the map can hold one entry per word. The two-pointer and in-place techniques in Common Interview Patterns exist precisely to get O(1) space where a naive solution would use O(n).

Recursion also consumes space: each nested call adds a stack frame, so a recursion that goes n levels deep uses O(n) space even if it allocates nothing.

Best, worst, and amortized

• Big-O conventionally describes the worst case unless stated otherwise. Quicksort is O(n log n) on average but O(n^2) in its worst case; hash lookups are O(1) on average but can degrade with pathological collisions.
• Amortized cost averages a rare expensive operation over many cheap ones. Array.prototype.push occasionally triggers a reallocation-and-copy, but averaged over many pushes it is O(1) — which is why push is treated as constant time everywhere in this section.