3 - Complejidad temporal

Analizamos las clases de complejidad temporal más comunes y cómo se reflejan en código Python. 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.

def obtener_primero(valores):
  if not valores:
    return -1  # caso vacio
  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.

def suma(valores):
  total = 0
  for valor in valores:
    total += valor  # O(1) por iteracion
  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.

def busqueda_binaria(valores, objetivo):
  ini = 0
  fin = len(valores) - 1
  while ini <= fin:
    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.

def mergesort(valores):
  if len(valores) <= 1:
    return valores
  medio = len(valores) // 2
  izquierda = mergesort(valores[:medio])
  derecha = mergesort(valores[medio:])
  return mezclar(izquierda, derecha)

def mezclar(izquierda, derecha):
  resultado = []
  i = 0
  j = 0
  while i < len(izquierda) and j < len(derecha):
    if izquierda[i] <= derecha[j]:
      resultado.append(izquierda[i])
      i += 1
    else:
      resultado.append(derecha[j])
      j += 1
  resultado.extend(izquierda[i:])
  resultado.extend(derecha[j:])
  return resultado

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.

def cuenta_mayores(valores):
  conteo = 0
  for i in range(len(valores)):
    for j in range(len(valores)):
      if valores[i] > valores[j]:
        conteo += 1  # 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