Rendimiento

Big O sin matemáticas

Respuesta corta: Big O describe cómo crece el trabajo cuando crece la entrada. O(n) significa que el trabajo se duplica si la entrada se duplica; O(n²) que se cuadruplica. Es una forma, no un cronómetro.

Por qué no basta con cronometrar

Cronometrar te dice sobre esta máquina en esta ejecución. Big O te dice qué pasa con 10 veces más entrada, en cualquier máquina. Compara dos formas de sumar 1..n:

#include <iostream>
using namespace std;

int main() {
    int n = 10;

    // forma 1: un bucle — n sumas
    int a = 0;
    for (int i = 1; i <= n; i++) a += i;

    // forma 2: la fórmula cerrada — siempre una multiplicación
    int b = n * (n + 1) / 2;

    cout << a << " " << b << endl;
    return 0;
}

Misma respuesta, crecimiento totalmente distinto. La forma 1 es O(n); la forma 2 es O(1) — constante, sin importar cuánto crezca n.

Las cuatro formas que de verdad verás

Cuenta el trabajo, no el tiempo

El truco es contar operaciones como función de n. Un solo bucle hace n:

#include <iostream>
using namespace std;

int main() {
    int n = 8;
    int pasos = 0;
    for (int i = 0; i < n; i++) {
        pasos++;            // una unidad de trabajo por vuelta
    }
    cout << "n = " << n << ", pasos = " << pasos << endl;
    return 0;
}

Ahora anídalo. El bucle interno corre n veces por cada una de las n vueltas externas:

#include <iostream>
using namespace std;

int main() {
    int n = 8;
    int pasos = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pasos++;
        }
    }
    cout << "n = " << n << ", pasos = " << pasos << " = n*n" << endl;
    return 0;
}

Cambia n a 4 y 16 en el código: los pasos van de 16 a 256. Eso es crecimiento cuadrático, y es la razón por la que un bucle anidado sobre 100.000 elementos es un problema.

Logarítmica: partir a la mitad

Cada pasada tira la mitad del rango restante, así que la cuenta crece como log₂(n):

#include <iostream>
using namespace std;

int main() {
    int n = 1000000;
    int pasos = 0;
    while (n > 1) {
        n /= 2;
        pasos++;
    }
    cout << "pasos para reducir 1000000 a 1: " << pasos << endl;
    return 0;
}

20 pasos para un millón. Por eso la búsqueda binaria es rápida, y por eso la comprobación de primalidad hasta √n gana a la división por tentativa.

Se tiran las constantes, se queda la forma

O(2n) se escribe O(n); O(n² + n) se escribe O(n²). Las constantes y los términos menores desaparecen porque con n grande manda el mayor. Así que dos bucles seguidos son O(n), no O(n²):

#include <iostream>
using namespace std;

int main() {
    int n = 8;
    int pasos = 0;
    for (int i = 0; i < n; i++) pasos++;     // n
    for (int i = 0; i < n; i++) pasos++;     // + n
    cout << "dos bucles separados: " << pasos << " = 2n, o sea O(n)" << endl;
    return 0;
}

Qué cambia esto en tu código

• Bucles anidados sobre los mismos datos son el culpable habitual de O(n²) — mira ¿Existe la suma de dos? y compáralo con lo que permitiría un array ordenado.
• Partir a la mitad es un superpoder. Cada vez que puedes descartar la mitad de los candidatos, estás en territorio log.
• Precalcular sale a cuenta. Sumas por rangos convierte O(n) por pregunta en O(1) tras una sola pasada O(n).

Preguntas de entrevista

1. ¿Cuál es la complejidad de este bucle? Cuenta cuántas veces corre la sentencia más interna en función de n y luego tira las constantes.
2. ¿Por qué ordenar suele ser O(n log n)? Porque la ordenación por comparaciones necesita n log n comparaciones en el peor caso — mejor que el O(n²) del ordenamiento burbuja.
3. ¿A Big O le importa la memoria? Esta notación no — la complejidad espacial es otra Big O sobre memoria. La ordenación por conteo cambia espacio por tiempo.

Relacionado: errores del compilador, vector frente a array, y la sección de práctica, donde cada análisis profundo indica su complejidad.