Big-O: Counting the Steps

Why we count steps, not seconds

In Lesson 11 we often said that one solution was “faster” than another. How can we know this before we run the code? A stopwatch does not help much. The same code runs at different speeds on a laptop and on a phone. And with a small input, almost every solution looks instant.

So we count steps instead. A step is one simple operation, such as a comparison, an addition or reading arr[i]. Then we ask one question: when the input gets bigger, how fast does the number of steps grow? We write the answer in Big-O notation. Big-O is a short way to describe how the work grows when the input size grows. Every interviewer uses it to talk about efficiency. The letter n always means the size of the input, for example the length of an array.

Counting the steps of a loop

Take one of the simplest loops, adding up an array, and count its steps:

function sum(nums) {  let total = 0;                              // 1 step  for (let i = 0; i < nums.length; i++) {     // n + 1 checks, n updates    total += nums[i];                         // n steps  }  return total;                               // 1 step}

If you add up the numbers in the comments, you get 1 + (n + 1) + n + n + 1 = 3n + 3 steps for an array of length n. (Different people count slightly different steps. For example, we did not count let i = 0. That is fine, as you will see.) Check the formula for a few sizes:

Big-O: keep only what grows

Exact counts like 3n + 3 depend on small details. For example, does i++ count as one step or as two? Big-O ignores such details. It uses two rules:

1. Drop constant factors. A constant factor is a fixed number that you multiply by. 3n and n grow in the same way: if you double n, the work doubles. So 3n becomes n.
2. Keep only the fastest-growing term. Look at n² + n + 3. When n is 1,000, the n² part is 1,000,000 and the rest is only about 1,000. The small terms stop mattering. So n² + n + 3 becomes n².

So the sum function is O(n). Say it “order n” or “linear time”. This measure of how the number of steps grows with the input is called time complexity.

The growth rates you will meet

Almost every solution in this series is one of these growth rates. They are in order from fastest to slowest:

The difference between these rates is very big. Here are the step counts as n grows:

O(log n): the halving loop

One growth rate needs more explanation. A logarithm (log for short) answers this question: how many times can I halve n before I reach 1? The small 2 in log₂ means “halve”.

• 16 → 8 → 4 → 2 → 1: four halvings, so log₂ 16 = 4.
• 1,024 → … → 1: ten halvings, so log₂ 1,024 = 10.
• 1,000,000 → … → 1: about twenty halvings.

So any loop that throws away half of what is left on each step is O(log n). It grows very slowly. Even for a billion items, it runs only about 30 times.

In Big-O, the base of the logarithm does not matter. (Dividing by 10 instead of 2 changes the work only by a constant factor.) So we just write log n. You have already met one such loop. The digit loop from Lesson 5 divides by 10 each time, so it is O(log n) in the size of the number.

Traced: halving 16 down to 1

▶let n = 16;2let steps = 0;3while (n > 1) {4  n = Math.floor(n / 2);5  steps++;6}7console.log(steps);

Reading Big-O from code

You rarely need to count exactly. Look at the shape of the loops instead. Here are four rules:

• One after another → add. Two separate loops over n are n + n = 2n, which is O(n).
• One inside another → multiply. A loop of n inside a loop of n is n × n = O(n²).
• Halving or doubling → log. A loop variable that is multiplied or divided by 2 each time gives O(log n).
• Two inputs → two letters. If there are two arrays of lengths n and m, write O(n + m) or O(n × m). Do not merge them into one n.

// O(1) — the same work for any nconst first = nums[0];// O(n) — one loop over the inputfor (let i = 0; i < n; i++) { /* ... */ }// O(n) — two loops one after the other: n + n = 2n → O(n)for (let i = 0; i < n; i++) { /* ... */ }for (let j = 0; j < n; j++) { /* ... */ }// O(n²) — a loop inside a loop: n × nfor (let i = 0; i < n; i++) {  for (let j = 0; j < n; j++) { /* ... */ }}// O(n²) — the inner loop starts at i + 1: about n²/2, still O(n²)for (let i = 0; i < n; i++) {  for (let j = i + 1; j < n; j++) { /* ... */ }}// O(log n) — the loop variable doubles (or n halves) each timefor (let i = 1; i < n; i *= 2) { /* ... */ }// O(n + m) — two different inputs, one after the otherfor (const a of arrA) { /* ... */ }for (const b of arrB) { /* ... */ }// O(n × m) — two different inputs, one inside the otherfor (const a of arrA) {  for (const b of arrB) { /* ... */ }}

Hidden loops in built-in methods

Some JavaScript methods look like one step, but they run a loop inside. If you put one of these inside your own loop, an O(n) solution becomes O(n²). You will not see a nested loop in your code, but it is there.

// Looks like one loop, but it is really two.function commonValues(a, b) {  const result = [];  for (const x of a) {           // runs n times    if (b.includes(x)) {         // includes scans b: up to m steps      result.push(x);    }  }  return result;                 // O(n × m) in total}// Same result, but only one pass over each arrayfunction commonValuesFast(a, b) {  const inB = new Set(b);        // m steps, once  const result = [];  for (const x of a) {           // n times    if (inB.has(x)) {            // 1 step      result.push(x);    }  }  return result;                 // O(n + m)}

Space complexity

Time is not the only cost. Space complexity measures how much extra memory a solution needs as the input grows. We do not count the input itself. We use the same Big-O notation for it.

Many improvements trade space for time. This means you use more memory to save time. In the hidden-loop example above, commonValuesFast uses an extra Set (O(m) space). In return, the time drops from O(n × m) to O(n + m). This is usually a good trade. Be ready to say it out loud, for example: “this is O(n) time and O(n) extra space”. Interviewers expect both numbers.

Best, average and worst case

The same code can do very different amounts of work for different inputs. Take linear search:

function indexOf(nums, target) {  for (let i = 0; i < nums.length; i++) {    if (nums[i] === target) return i;  }  return -1;}

Unless someone says otherwise, we quote the worst case. It is the only one you can promise, because the best case depends on luck. The common exception is Map and Set. For them we quote the average case, O(1), because the worst case almost never happens in practice.

From constraints to approach

This is where Big-O helps you most in interviews. Take the constraints (Lesson 11) and the rule of thumb of about 10⁸ simple steps per second. Then the size of n tells you which growth rate you need before you design the solution:

Practice questions

For every solution below, say its time complexity and space complexity before you read the explanation. Saying both numbers should become automatic for you.

// Afor (let i = 0; i < n; i++)  for (let j = 0; j < n; j++) work();// Bfor (let i = 0; i < n; i++) work();for (let j = 0; j < n; j++) work();// Cfor (let i = 1; i < n; i *= 2) work();// Dfor (let i = 0; i < n; i++)  for (let j = 0; j < i; j++) work();// Efor (let i = 0; i < n; i++)  for (let j = 0; j < 5; j++) work();// Ffor (const x of nums) if (other.includes(x)) work();   // both arrays have length n

function count(n) {  const c = { A: 0, B: 0, C: 0, D: 0, E: 0 };  for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) c.A++;  for (let i = 0; i < n; i++) c.B++;  for (let j = 0; j < n; j++) c.B++;  for (let i = 1; i < n; i *= 2) c.C++;  for (let i = 0; i < n; i++) for (let j = 0; j < i; j++) c.D++;  for (let i = 0; i < n; i++) for (let j = 0; j < 5; j++) c.E++;  return c;}console.log(count(10));   // { A: 100, B: 20, C: 4, D: 45, E: 50 }console.log(count(100));  // { A: 10000, B: 200, C: 7, D: 4950, E: 500 }console.log(count(1000)); // { A: 1000000, B: 2000, C: 10, D: 499500, E: 5000 }

// A  n × n                 → O(n²)// B  n + n = 2n             → O(n)// C  1, 2, 4 … < n          → O(log n)// D  0 + 1 + … + (n-1)      → n(n-1)/2 → O(n²)// E  n × 5                  → O(n)// F  n × (includes: n)      → O(n²)

function sumTo(n) {  let total = 0;  for (let i = 1; i <= n; i++) total += i;  return total;}console.log(sumTo(5)); // 15

function sumTo(n) {  return (n * (n + 1)) / 2;}console.log(sumTo(5));         // 15console.log(sumTo(100000000)); // 5000000050000000

function checkIfExist(arr) {  for (let i = 0; i < arr.length; i++) {    for (let j = 0; j < arr.length; j++) {      if (i !== j && arr[i] === 2 * arr[j]) return true;    }  }  return false;}console.log(checkIfExist([10, 2, 5, 3])); // trueconsole.log(checkIfExist([3, 1, 7, 11])); // falseconsole.log(checkIfExist([0, 0]));        // trueconsole.log(checkIfExist([0]));           // false

function checkIfExist(arr) {  const seen = new Set();  for (const x of arr) {    if (seen.has(2 * x) || seen.has(x / 2)) return true;    seen.add(x);  }  return false;}console.log(checkIfExist([10, 2, 5, 3])); // trueconsole.log(checkIfExist([3, 1, 7, 11])); // falseconsole.log(checkIfExist([0, 0]));        // trueconsole.log(checkIfExist([0]));           // false

function intersection(nums1, nums2) {  const result = [];  for (const x of nums1) {    if (nums2.includes(x) && !result.includes(x)) result.push(x);  }  return result;}console.log(intersection([1, 2, 2, 1], [2, 2]));       // [ 2 ]console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [ 4, 9 ]

function intersection(nums1, nums2) {  const inFirst = new Set(nums1);  const result = new Set();  for (const x of nums2) {    if (inFirst.has(x)) result.add(x);  }  return [...result];}console.log(intersection([1, 2, 2, 1], [2, 2]));       // [ 2 ]console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [ 9, 4 ]

function intersection(nums1, nums2) {  const a = [...nums1].sort((x, y) => x - y);  const b = [...nums2].sort((x, y) => x - y);  const result = [];  let i = 0, j = 0;  while (i < a.length && j < b.length) {    if (a[i] < b[j]) i++;    else if (a[i] > b[j]) j++;    else {      if (result[result.length - 1] !== a[i]) result.push(a[i]);      i++;      j++;    }  }  return result;}console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [ 4, 9 ]

function countDigits(n) {  if (n === 0) return 1;  let count = 0;  while (n > 0) {    n = Math.floor(n / 10);    count++;  }  return count;}console.log(countDigits(7));     // 1console.log(countDigits(12345)); // 5console.log(countDigits(0));     // 1

function countDigits(n) {  return String(n).length;}console.log(countDigits(12345)); // 5console.log(countDigits(0));     // 1

function countDigits(n) {  if (n === 0) return 1;  return Math.floor(Math.log10(n)) + 1;}console.log(countDigits(7));     // 1console.log(countDigits(12345)); // 5console.log(countDigits(1000));  // 4

function reversed(nums) {  const out = [];  for (let i = nums.length - 1; i >= 0; i--) out.push(nums[i]);  return out;}console.log(reversed([1, 2, 3, 4, 5])); // [ 5, 4, 3, 2, 1 ]console.log(reversed([]));              // []

function reverseInPlace(nums) {  let left = 0;  let right = nums.length - 1;  while (left < right) {    const tmp = nums[left];    nums[left] = nums[right];    nums[right] = tmp;    left++;    right--;  }  return nums;}console.log(reverseInPlace([1, 2, 3, 4, 5])); // [ 5, 4, 3, 2, 1 ]console.log(reverseInPlace([]));              // []

function findDisappearedNumbers(nums) {  const result = [];  for (let k = 1; k <= nums.length; k++) {    if (!nums.includes(k)) result.push(k);  }  return result;}console.log(findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1])); // [ 5, 6 ]

function findDisappearedNumbers(nums) {  const present = new Set(nums);  const result = [];  for (let k = 1; k <= nums.length; k++) {    if (!present.has(k)) result.push(k);  }  return result;}console.log(findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1])); // [ 5, 6 ]console.log(findDisappearedNumbers([1, 1]));                   // [ 2 ]

function findDisappearedNumbers(nums) {  for (const x of nums) {    const i = Math.abs(x) - 1;    if (nums[i] > 0) nums[i] = -nums[i];  }  const result = [];  for (let i = 0; i < nums.length; i++) {    if (nums[i] > 0) result.push(i + 1);  }  return result;}console.log(findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1])); // [ 5, 6 ]console.log(findDisappearedNumbers([1, 1]));                   // [ 2 ]

Make it stick

What's next

You can now read a problem carefully and judge how fast a solution must be. Lesson 13 covers basic maths that appears in many problems: divisors, prime numbers, the greatest common divisor and fast powers. Several of these ideas turn an O(n) loop into O(√n) or O(log n). You now have the words to say exactly why that matters.