3 - Complejidad temporal

Analizamos las clases de complejidad temporal más comunes y cómo se reflejan en código C. Cada subsección incluye una intuición y un ejemplo breve.

3.1 Operaciones básicas: O(1)

El tiempo no depende del tamaño de entrada. Acceder a una posición de un array o apilar un elemento en una pila implementada con índices es constante.

int obtener_primero(const int *valores, int n) {
  if (n == 0) {
    return -1; // caso vacío
  }
  return valores[0]; // O(1)
}

3.2 Lineal: O(n)

El trabajo crece proporcional a n. Recorrer una lista o un array completo es un patrón clásico.

long suma(const int *valores, int n) {
  long total = 0;
  for (int i = 0; i < n; i++) {
    total += valores[i]; // O(1) por iteración
  }
  return total; // O(n) total
}

3.3 Logarítmica: O(log n)

Se reduce el problema a la mitad en cada paso. La búsqueda binaria en un arreglo ordenado es el ejemplo habitual.

int busqueda_binaria(const int *valores, int n, int objetivo) {
  int ini = 0, fin = n - 1;
  while (ini <= fin) {
    int medio = (ini + fin) / 2;
    if (valores[medio] == objetivo) return medio;
    if (valores[medio] < objetivo) {
      ini = medio + 1;
    } else {
      fin = medio - 1;
    }
  }
  return -1; // no encontrado
}

3.4 Lineal-logarítmica: O(n log n)

Combina trabajo lineal por nivel y log n niveles de división. Los ordenamientos por comparación bien diseñados caen en esta categoría.

void mergesort(int *valores, int inicio, int fin, int *buffer) {
  if (inicio >= fin) return;
  int medio = (inicio + fin) / 2;
  mergesort(valores, inicio, medio, buffer);
  mergesort(valores, medio + 1, fin, buffer);
  // mezcla lineal de dos mitades
  int i = inicio, j = medio + 1, k = inicio;
  while (i <= medio && j <= fin) {
    buffer[k++] = (valores[i] <= valores[j]) ? valores[i++] : valores[j++];
  }
  while (i <= medio) buffer[k++] = valores[i++];
  while (j <= fin) buffer[k++] = valores[j++];
  for (int t = inicio; t <= fin; t++) valores[t] = buffer[t];
}

3.5 Cuadrática: O(n^2)

Dos bucles anidados que recorren la misma entrada generan crecimiento cuadrático. Es común en comparaciones par a par.

int cuenta_mayores(const int *valores, int n) {
  int conteo = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (valores[i] > valores[j]) {
        conteo++; // O(n^2) comparaciones
      }
    }
  }
  return conteo;
}

3.6 Polinómica, exponencial y factorial

Polinómica: exponente fijo mayor a 2, como O(n^3) al multiplicar matrices con el algoritmo básico de tres bucles anidados.

Exponencial: O(2^n), crece al duplicar trabajo por cada elemento; explora combinaciones.

Factorial: O(n!), explora permutaciones; impracticable salvo para n muy pequeños.

3.7 Tabla comparativa

Comparación de crecimiento aproximado al duplicar n (de 1 000 a 2 000):

Complejidad	Trabajo relativo al duplicar n	Ejemplo
O(1)	Igual	Acceder a un índice
O(log n)	+1 paso aprox.	Búsqueda binaria
O(n)	2×	Recorrido completo
O(n log n)	~2.2×	MergeSort
O(n^2)	4×	Bucles anidados
O(2^n)	2× por elemento extra	Subconjuntos