← Data structures from scratch · Lesson 3/32

What it costs: Big O

1/8

Count steps, not seconds

How long a program takes depends on the computer, the phone, what else is open. So we measure something else: how many steps it takes depending on the size of the input, called n.

This function adds up an array and counts its loop turns. With 3 items it takes 3 steps; with 1000, 1000. The work grows just like n: we say it's O(n), "order n" or linear.

leccion.js

1function suma(arr) {
2  let total = 0, pasos = 0;
3  for (const x of arr) {
4    total += x;
5    pasos++;
6  }
7  console.log("n =", arr.length, "pasos =", pasos);
8  return total;
9}
10
11suma([4, 5, 6]);
12suma(new Array(1000).fill(1));

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

Steps and n come out equal: if the array doubles, so does the work.

The whole lesson on one page

Count steps, not seconds

How long a program takes depends on the computer, the phone, what else is open. So we measure something else: how many steps it takes depending on the size of the input, called n.

This function adds up an array and counts its loop turns. With 3 items it takes 3 steps; with 1000, 1000. The work grows just like n: we say it's O(n), "order n" or linear.

1function suma(arr) {
2  let total = 0, pasos = 0;
3  for (const x of arr) {
4    total += x;
5    pasos++;
6  }
7  console.log("n =", arr.length, "pasos =", pasos);
8  return total;
9}
10
11suma([4, 5, 6]);
12suma(new Array(1000).fill(1));

Steps and n come out equal: if the array doubles, so does the work.

When everyone is compared with everyone

If for each item you walk the array again (two loops, one inside the other), the steps grow like n × n: O(n²), quadratic. With 10 items it's 45 pairs; with 1000, almost half a million.

Big O ignores constants and small terms: n²/2 is still O(n²). What matters is the shape of the growth as n gets huge.

1function parejas(n) {
2  let pasos = 0;
3  for (let i = 0; i < n; i++)
4    for (let j = i + 1; j < n; j++)
5      pasos++;
6  return pasos;
7}
8
9for (const n of [10, 100, 1000]) {
10  console.log(n, "->", parejas(n));
11}

Each time n grows tenfold, the steps grow about a hundredfold. That's what O(n²) looks like.

Halving: O(log n)

The opposite of growing fast: if each step throws away half of what's left, a million is done in 20 steps. That's O(log n), logarithmic, and it's why searching something sorted is so fast.

The families, cheapest to most expensive:

O(1) constant: reading arr[5].
O(log n): binary search.
O(n): one pass.
O(n log n): sorting well.
O(n²): comparing everything with everything.
O(2ⁿ): trying every combination.

1function mitades(n) {
2  let pasos = 0;
3  while (n > 1) {
4    n = Math.floor(n / 2);
5    pasos++;
6  }
7  return pasos;
8}
9
10for (const n of [8, 1024, 1_000_000]) {
11  console.log(n, "->", mitades(n));
12}

A million in 19 steps. Multiplying n by a thousand only adds about 10 steps.