Big-O Basics

Your program works on ten items in development, but in production it needs to handle ten thousand. The code that felt instant suddenly takes seconds, then minutes. The difference between a solution that scales and one that collapses is usually a single algorithmic choice made early — and the tool for describing that choice is Big-O notation.

Big-O tells you how much an algorithm's cost grows as its input grows. It is not about milliseconds on your laptop; it is about the shape of the growth curve. Two algorithms that both solve the same problem can have wildly different curves, and Big-O gives you a shared vocabulary for comparing them without running either one.

graph TD
  A["Input size n"] --> B["O(1): flat"]
  A --> C["O(log n): slow climb"]
  A --> D["O(n): steady slope"]
  A --> E["O(n²): steep curve"]
  style B fill:#1e7f3d,color:#fff
  style E fill:#b91c1c,color:#fff

Common growth curves: constant stays flat, linear climbs steadily, quadratic explodes.

The anatomy of Big-O

The O stands for order of growth. When we say an algorithm is O(n), we mean that if the input size doubles, the work roughly doubles too. The n is the input size — the number of items in an array, the length of a string, the nodes in a tree. The function inside the parentheses describes the relationship between input size and work.

Big-O has three simplifying rules that make it portable across machines and languages. First, drop constants: O(2n) becomes O(n) because we care about the shape of the curve, not the exact multiplier. A loop that does two operations per item is still linear. Second, keep only the dominant term: O(n² + n) becomes O(n²) because when n is large, the squared term swamps the linear one. Third, we measure the worst case unless stated otherwise — the upper bound on what the algorithm might have to do in the most unlucky arrangement of its input.

These rules make Big-O a rough guide, not an exact accounting. It is designed to answer one question: as the input grows without bound, what happens to the work?

A single loop is O(n): the work scales with the input size. Press Run.

const items = [10, 20, 30, 40];

// O(1) — read by index
console.log(items[2]);

// O(n) — scan to find a value
let found = false;
for (const x of items) {
  if (x === 30) found = true;
}
console.log(found);

Reading code like a complexity detective

To analyse a function, count the operations that grow with n and ignore everything that stays flat. A single loop from 0 to n-1 does n iterations of constant work, so it is O(n). Two separate loops back-to-back are O(2n), which simplifies to O(n) because constants disappear. A loop inside a loop is O(n²) because the inner body runs n × n times. A loop that halves its range each iteration, like jumping to the middle of a sorted array, is O(log n). The key is to look for the loops and recursive calls, then ask: what controls how many times this runs?

The usual suspects

You will meet the same few curves again and again. O(1) means constant time — the work stays flat no matter how large the input gets, like reading the first element of an array. O(log n) means the work grows slowly, halving the problem each step, like binary search. O(n) means the work scales linearly, like a single loop that visits every item once. O(n log n) is the signature of efficient sorting algorithms. O(n²) means the work explodes, like nested loops that compare every item with every other item. Memorising these shapes lets you glance at code and know which family it belongs to.

graph LR
  A["O(2n + 5)"] -->|"drop constants"| B["O(n)"]
  C["O(n² + n)"] -->|"keep dominant"| D["O(n²)"]
  style B fill:#e0900b,color:#fff
  style D fill:#e0900b,color:#fff

Simplification rules: drop constants and keep only the dominant term.

Nested loops multiply: an inner loop running n times inside an outer loop running n times is O(n²).

const nums = [1, 2, 3];
let pairs = 0;
for (let i = 0; i < nums.length; i++) {
  for (let j = 0; j < nums.length; j++) {
    pairs++;
  }
}
console.log(pairs);

Space complexity

Time is not the only resource that matters. Every array you build, every recursive call waiting on the stack, and every temporary object consumes memory. Space complexity uses the same Big-O notation to describe how memory usage grows with input size.

A function that sorts an array in place might use O(1) extra space — only a few variables — while one that copies the whole array into a new structure uses O(n). Recursive algorithms often hide space costs in the call stack; a recursive function that calls itself n times uses O(n) stack space even if each frame only stores a single number.

The best solutions often trade one for the other: using a hash table to cache results trades O(n) memory for O(1) lookup time, while keeping memory tiny sometimes means doing extra passes over the data. Understanding both axes lets you choose the right trade-off for the constraints you face.

flowchart TD
  A["Need fast lookup?"] -->|"O(n) time"| B["Scan array"]
  A -->|"O(1) time<br/>O(n) space"| C["Use a Set"]
  style C fill:#3776ab,color:#fff

Time vs space: using extra memory can turn a slow scan into a fast lookup.

Building a copy uses O(n) extra space because the new array grows with the input.

function buildCopy(arr) {
  const copy = [];
  for (const x of arr) copy.push(x);
  return copy;
}
console.log(buildCopy([1, 2, 3]).length);

Exercise

What does this print? Track the loop and the final value of sum.

const data = [1, 2, 3, 4];
let sum = 0;
for (let i = 0; i < data.length; i++) {
  sum += data[i];
}
console.log(sum);

Your prediction — what does this print?

Exercise

Write hasDuplicate(arr) that returns true if any value appears more than once. Use a Set so the function runs in O(n) time.

function hasDuplicate(arr) {
  // use a Set for O(n) time
}

function hasDuplicate(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Exercise

This function builds an array of the first n numbers and returns the sum. It works, but it uses unshift inside a loop, making it O(n²). Fix it to use push instead so it becomes O(n).

function sumFirstN(n) {
  const arr = [];
  for (let i = 1; i <= n; i++) {
    arr.unshift(i);
  }
  let sum = 0;
  for (const x of arr) sum += x;
  return sum;
}

function sumFirstN(n) {
  const arr = [];
  for (let i = 1; i <= n; i++) {
    arr.push(i);
  }
  let sum = 0;
  for (const x of arr) sum += x;
  return sum;
}

Exercise

Which of these array operations is O(1)?

Exercise

Write findPair(arr, target) that returns true if any two distinct numbers in arr add up to target. It should run in O(n) time by using a Set to remember the numbers you have seen so far.

function findPair(arr, target) {
  // use a Set for O(n) time
}

function findPair(arr, target) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(target - x)) return true;
    seen.add(x);
  }
  return false;
}

Recap

Big-O describes the shape of growth, not exact seconds.
Drop constants and keep only the dominant term.
Measure the worst-case scenario unless told otherwise.
Space complexity tracks memory growth the same way time complexity tracks work.
Hidden costs like unshift or splice can turn an apparently fast loop into a slow one.

Next you will meet the two foundational sequential data structures — arrays and linked lists — and learn why the right choice between them depends on exactly the complexity costs you just studied.

The anatomy of Big-O

Reading code like a complexity detective

The usual suspects

Space complexity

Recap

Checkpoint quiz

Go deeper — technical resources