Big-O: how long your code takes as the data grows
O(1), O(n), O(log n), O(n²)... with a visualiser that compares linear and binary search by counting steps.
Big-O does not measure seconds: it measures how the work GROWS as the data grows. An O(n) algorithm with twice the data takes twice as long; an O(n²) one, four times as long. That is why it matters before your program gets slow with real data.
Linear vs binary: watch it
Las dos buscan un número en una lista ordenada. La lineal mira uno a uno; la binaria descarta la mitad en cada paso. Sube el tamaño y compara las comparaciones:
Search comparatorinteractivo
The complexities you will see
| Notación | Nombre | Ejemplo típico | 1 000 datos ≈ |
|---|---|---|---|
O(1) | constante | acceder a lista[5], mapa.get(k) | 1 paso |
O(log n) | logarítmica | búsqueda binaria, árboles equilibrados | ~10 pasos |
O(n) | lineal | recorrer una lista, max(), búsqueda lineal | 1 000 pasos |
O(n log n) | casi lineal | ordenar bien (sort, merge sort) | ~10 000 pasos |
O(n²) | cuadrática | dos bucles anidados, comparar todos con todos | 1 000 000 pasos |
O(2ⁿ) | exponencial | fuerza bruta, Fibonacci recursivo ingenuo | inviable |
Spotting it in the code
// O(1): no depende del tamaño
function primero(lista) { return lista[0]; }
// O(n): un bucle sobre los datos
function suma(lista) {
let total = 0;
for (const x of lista) total += x; // n iteraciones
return total;
}
// O(n²): un bucle dentro de otro
function hayDuplicados(lista) {
for (let i = 0; i < lista.length; i++)
for (let j = i + 1; j < lista.length; j++) // n · n
if (lista[i] === lista[j]) return true;
return false;
}
// O(n): el mismo problema con un Set
function hayDuplicados2(lista) {
const vistos = new Set();
for (const x of lista) {
if (vistos.has(x)) return true; // has() es O(1)
vistos.add(x);
}
return false;
}Quick rule: each loop nested over the data multiplies by n. A
Set or a Map usually brings an O(n²) down to O(n).Check what you've learned
¿Cuál es la complejidad de dos bucles
for anidados sobre una lista de n elementos?La búsqueda binaria sobre 1 000 elementos hace aproximadamente…
Next step
Data structures visualised · Sorting and searching algorithms