Master theorem

Cuando un algoritmo se define recursivamente con la forma "divido el problema en a subproblemas de tamaño n/b, después combino los resultados en O(n^d) tiempo", la complejidad sigue un patrón predecible. El master theorem es la fórmula que captura ese patrón.

La recurrencia estándar

Un algoritmo divide-y-vencerás se describe con una recurrencia:

T(n) = a · T(n/b) + O(n^d)

Donde:

• a es la cantidad de subproblemas que generás en cada llamada.
• b es la fracción del input que va a cada subproblema (típicamente 2 si divides a la mitad).
• d es el exponente del costo de "combinar" los subresultados (excluyendo el trabajo recursivo).

Ejemplos:

• Merge sort: T(n) = 2·T(n/2) + O(n). Divides en dos mitades, cada mitad se ordena recursivamente, después combinas en O(n).
• Búsqueda binaria: T(n) = 1·T(n/2) + O(1). Una sola subllamada, sobre la mitad, combinas en O(1).
• Quick sort (peor caso): T(n) = T(n-1) + O(n). No es divide-y-vencerás clásico, esta forma no se ajusta al master theorem.

Los tres casos

Comparás a con b^d:

Caso 1: a < b^d → El trabajo de combinar domina. T(n) = O(n^d)

Caso 2: a = b^d → Equilibrio entre subproblemas y combinación. T(n) = O(n^d · log n)

Caso 3: a > b^d → Los subproblemas dominan. T(n) = O(n^(log_b a))

Aplicar a los ejemplos

Merge sort: a=2, b=2, d=1. b^d = 2^1 = 2. a = b^d. Caso 2: O(n · log n). ✓

Búsqueda binaria: a=1, b=2, d=0. b^d = 2^0 = 1. a = b^d. Caso 2: O(n^0 · log n) = O(log n). ✓

Karatsuba (multiplicación rápida): T(n) = 3·T(n/2) + O(n). a=3, b=2, d=1. b^d = 2. a > b^d. Caso 3: O(n^(log_2 3)) ≈ O(n^1.585). Más rápido que la multiplicación O(n²) tradicional.

Strassen (multiplicación de matrices): T(n) = 7·T(n/2) + O(n²). a=7, b=2, d=2. b^d = 4. a > b^d. Caso 3: O(n^(log_2 7)) ≈ O(n^2.807). Más rápido que el O(n³) ingenuo.

La intuición de los tres casos

El árbol de recursión tiene log_b n niveles. En cada nivel hay a^k subproblemas (k = nivel actual), cada uno de tamaño n/b^k, con costo de combinar O((n/b^k)^d).

• Si a < b^d: el costo decrece con cada nivel. La raíz domina. Total: O(n^d).
• Si a = b^d: cada nivel cuesta lo mismo. Hay log n niveles. Total: O(n^d · log n).
• Si a > b^d: el costo crece con cada nivel. Las hojas dominan. Total: O(n^(log_b a)).

No necesitas memorizar la intuición. Memorizá los tres casos y el método de comparación.

Cuándo NO usar master theorem

El master theorem solo aplica a recurrencias de la forma estándar T(n) = a·T(n/b) + O(n^d) con a ≥ 1 y b > 1. No aplica cuando:

• Los subproblemas tienen tamaños distintos: T(n) = T(n/3) + T(2n/3) + O(n).
• La recursión es lineal: T(n) = T(n-1) + O(n) (esto es O(n²) por suma directa, no por master).
• El costo no es polinomial: T(n) = 2·T(n/2) + O(n log n) (caso "log" extra requiere otra fórmula).

Para estos hay variantes (Akra-Bazzi, recurrence tree directo). En entrevistas casi nunca te piden tanto detalle.

La trampa típica

Cuando ves un algoritmo recursivo en una entrevista, escribe la recurrencia primero, después aplica master theorem. No saltes a "esto es O(n log n) porque es como merge sort" si no verificaste.

Por ejemplo: dada una función f(n) que llama a f(n/2) tres veces y hace O(n²) de trabajo interno, ¿cuál es la complejidad?

Recurrencia: T(n) = 3·T(n/2) + O(n²). a=3, b=2, d=2. b^d = 4 > a. Caso 1: O(n²). La recursión no domina, el trabajo cuadrático sí.

Para usar en entrevistas

Casi siempre vas a usar el master theorem implícitamente:

• Merge sort → O(n log n)
• Búsqueda binaria → O(log n)
• DP con memoización donde guardas N estados y cada uno requiere O(1) → O(N)

Pero saberlo formalmente sirve cuando te dan un algoritmo recursivo no estándar y tienes que justificar el costo. Di: "La recurrencia es T(n) = a·T(n/b) + f(n). Por master theorem, caso X, la complejidad es Y."