AALIE

Método de Suposiciones Inteligentes

Verificación inductiva de cotas para recurrencias mediante sustitución.

Cuándo usar Suposiciones Inteligentes

El método de Suposiciones Inteligentes, también llamado método de sustitución, se usa cuando ya tienes una candidata razonable para la solución de una recurrencia y necesitas verificarla formalmente.

No es un método para adivinar mágicamente. Primero se obtiene una intuición con árbol de recursión, comparación con recurrencias conocidas, sumas por niveles o patrones de crecimiento. Luego se prueba la cota mediante inducción.

Cuándo usar sustitución

Situación	Uso del método	Riesgo
La recurrencia se parece a una ya resuelta	Proponer la misma forma y verificar por inducción.	Copiar una respuesta parecida sin comprobar constantes.
Teorema Maestro básico no aplica	Usar árbol o intuición para proponer una cota y luego probarla.	Forzar un caso del Teorema Maestro que no existe.
Hay llamados de distinto tamaño	Probar cotas superiores e inferiores por sustitución.	Tratar la recurrencia como balanceada cuando no lo es.
Ya se obtuvo una respuesta por otro método	Usar sustitución como verificación formal.	Creer que una intuición visual reemplaza la demostración.

No es adivinanza

Una suposición no es una solución. Es solo una candidata. La solución empieza cuando logras demostrar la desigualdad con inducción y constantes explícitas.

Idea central del método

La idea central es reemplazar los términos recursivos por la cota que quieres demostrar. Si quieres probar una cota superior, reemplazas cada $T (k)$ por algo que lo acota por arriba. Si quieres probar una cota inferior, lo reemplazas por algo que lo acota por abajo.

Formas inductivas más usadas

Objetivo	Suposición	Hipótesis inductiva	Meta
$T (n) \in O (g (n))$	$T (n) \leq C g (n)$	$T (k) \leq C g (k) para k < n$	$T (n) \leq C g (n)$
$T (n) \in Ω (g (n))$	$T (n) \geq c g (n)$	$T (k) \geq c g (k) para k < n$	$T (n) \geq c g (n)$
$T (n) \in Θ (g (n))$	$c_{1} g (n) \leq T (n) \leq c_{2} g (n)$	Probar O y Ω por separado	$T (n) \in O (g (n)) \land T (n) \in Ω (g (n))$

Clave práctica

Para empezar, suele ser más cómodo probar $O$ en vez de $Θ$ . La cota superior tiene margen: puedes elegir una constante grande para absorber términos menores. Después, si hace falta, pruebas $Ω$ por separado.

Paso a paso — Sustitución

Proponer una forma candidata. Usa árbol, intuición de niveles, método previo o comparación con una recurrencia conocida.
Traducir la notación a desigualdad. Por ejemplo, $T (n) \in O (n lo g n)$ se traduce como $T (n) \leq C n lo g n$ .
Formular la hipótesis inductiva. Supón que la desigualdad ya se cumple para todo $k < n$ .
Sustituir en la recurrencia. Reemplaza cada llamado recursivo $T (k)$ por la expresión de la hipótesis.
Simplificar. Expande logaritmos, agrupa términos y separa lo dominante de lo residual.
Cerrar la desigualdad. Elige constantes o un $n_{0}$ suficiente para que la desigualdad final quede probada.
Verificar casos base. Si los primeros valores no cumplen, se ajusta $n_{0}$ . Eso es válido porque las cotas asintóticas aplican desde cierto punto en adelante.
Concluir. Si probaste cota superior, concluye $O$ . Si además probaste cota inferior, concluye $Θ$ .

Esqueleto de prueba para cota superior

Proponer la cota

La notación se convierte en una desigualdad concreta con una constante positiva.

T (n) \in O (g (n)) ⟺ T (n) \leq C g (n)

Hipótesis inductiva

La recurrencia llama tamaños menores que $n$ , por eso se puede usar esta hipótesis sobre los subproblemas.

T (k) \leq C g (k) para todo k < n

Sustituir

Cada término recursivo se reemplaza por su cota inductiva.

T (n) = recurrencia \leq expresi \overset{o}{ˊ} n con C g (k)

Cerrar

Aquí se elige $C$ suficientemente grande o $n_{0}$ suficientemente grande.

expresi \overset{o}{ˊ} n obtenida \leq C g (n)

Ejemplo base — T(n)=2T(n/2)+cn

Queremos verificar por sustitución que la recurrencia $T (n) = 2 T (n /2) + c n$ tiene cota superior $O (n lo g n)$ .

Prueba de O(n log n)

Suposición

La cota candidata viene del árbol de recursión o del Teorema Maestro.

T (n) \leq C n lo g n

Hipótesis inductiva

En particular se puede usar con $k = n /2$ .

T (k) \leq C k lo g k para k < n

Sustituir

Se reemplaza $T (n /2)$ usando la hipótesis inductiva.

T (n) = 2 T (n /2) + c n \leq 2 C \frac{n}{2} lo g (n /2) + c n

Expandir logaritmo

Usando logaritmo base 2, $lo g (n /2) = lo g n - 1$ .

2 C \frac{n}{2} lo g (n /2) + c n = C n (lo g n - 1) + c n

Agrupar

El término residual será no positivo si $C \geq c$ .

C n lo g n - C n + c n = C n lo g n - n (C - c)

Cerrar desigualdad

Elegir $C$ suficientemente grande permite cerrar la prueba.

C \geq c \Rightarrow T (n) \leq C n lo g n

Resultado

Se confirma que $T (n) \in O (n lo g n)$ . Para concluir $Θ (n lo g n)$ hace falta probar también la cota inferior $Ω (n lo g n)$ , o justificarla con otro método válido.

Trampa de caso base

Si $T (1) = 1$ , la desigualdad $T (1) \leq C \cdot 1 \cdot lo g 1$ falla porque $lo g 1 = 0$ . No se descarta la prueba: se ajusta $n_{0}$ y se toman los primeros valores como casos base inductivos.

Cómo elegir una suposición inteligente

La parte difícil del método no es sustituir. La parte difícil es escoger una cota que tenga posibilidades reales de cerrar. Si escoges una cota demasiado pequeña, la prueba falla. Si escoges una cota demasiado grande, puede cerrar pero ser inútil o poco precisa.

Fuentes para proponer la cota

Fuente	Pregunta útil	Ejemplo
Árbol de recursión	¿Cuánto cuesta cada nivel y cuántos niveles hay?	$2 T (n /2) + n / l o g n \Rightarrow n lo g lo g n$
Teorema Maestro	¿La recurrencia se parece a un caso conocido aunque no encaje exactamente?	$2 T (n /2) + n \Rightarrow n lo g n$
Dominancia del término externo	¿El costo local domina a los subproblemas?	$T (n /2) + n \Rightarrow n$
Suma geométrica	¿Los costos por nivel decrecen con razón menor que 1?	$T (n /2) + n \Rightarrow n$
Caso conocido	¿Ya resolviste una forma casi igual?	$T (n /3) + T (2 n /3) + n \Rightarrow n lo g n$

Elección de la suposición

Renderizando diagrama...

Técnicas para cerrar la prueba

Cerrar una prueba por sustitución casi siempre consiste en manejar un término residual. Ese residual puede desaparecer con una constante grande, con un $n_{0}$ suficientemente grande o con una hipótesis inductiva más fuerte.

Técnicas comunes de cierre

Técnica	Cuándo usarla	Forma típica
Elegir C grande	Cuando aparece un término como $- n (C - c)$	$C \geq c$
Ajustar n₀	Cuando la desigualdad solo falla en valores pequeños.	$n \geq n_{0}$
Usar margen negativo	Cuando la cota simple deja un término positivo imposible de absorber.	$T (n) \leq C g (n) - h (n)$
Probar O y Ω por separado	Cuando quieres concluir $Θ$	$O (g (n)) \land Ω (g (n))$
Cambiar la suposición	Cuando la cota propuesta es falsa o demasiado débil para cerrar.	$n lo g n \to n lo g lo g n$

Cuando la prueba no cierra

Que una prueba no cierre no implica automáticamente que la cota sea falsa. A veces la cota es correcta, pero la hipótesis inductiva es demasiado débil. En esos casos se fortalece con un término de margen.

Taller de Desafíos Propuestos

Como práctica de consolidación, se propone el siguiente taller de desafíos. Para cada recurrencia, intenta primero obtener una intuición visual con un árbol y luego demuestra formalmente la cota mediante el método de sustitución.

Guía de desafíos: Recurrencia y suposición candidata

Recurrencia	Candidato	Intuición	Tipo de prueba sugerida
$T (n) = T (n /2) + T (n) + n$	$Θ (n)$	El término $+ n$ domina los subproblemas.	Sustitución directa para O y cota inferior inmediata.
$T (n) = 2 T (n /2) + \frac{n}{l o g n}$	$Θ (n lo g lo g n)$	Costo por nivel $n / (lo g n - i)$ ; suma armónica sobre niveles.	Sustitución con log log e inequalities para n grande.
$T (n) = 2 T (n /2) + \frac{n}{( l o g n ) ^{2}}$	$Θ (n)$	La suma de $1/ j^{2}$ converge.	Requiere hipótesis fortalecida para O.
$T (n) = T (n /2) + \frac{n}{l o g n}$	$Θ (\frac{n}{l o g n})$	Los niveles decrecen geométricamente y domina la raíz.	Sustitución directa con n suficientemente grande.
$T (n) = T (n /3) + T (2 n /3) + n$	$Θ (n)$	Las hojas aportan masa lineal; el término $n$ no domina.	O con hipótesis fortalecida y Ω por hojas o monotonía.
$T (n) = T (n /2) + n$	$Θ (n)$	Serie geométrica decreciente en $n$ .	Sustitución directa.
$T (n) = T (n /2) + T (n /4) + n$	$Θ (n)$	La suma de tamaños de subproblemas es $3 n /4$ ; domina la raíz.	Sustitución directa para O y Ω inmediata por el término n.

Ejemplo 1 — T(n)=T(n/2)+T(√n)+n

El término local $+ n$ sugiere una cota lineal. Probamos $T (n) \in O (n)$ por sustitución.

Prueba de cota superior

Suposición

La candidata es lineal.

T (n) \leq C n

Hipótesis inductiva

Se aplica a $n /2$ y a $n$ para $n > 1$ .

T (k) \leq C k para k < n

Sustituir

Se acotan ambos subproblemas.

T (n) \leq C \frac{n}{2} + C n + n

Cerrar

Equivale a $C (n /2 - n) \geq n$ . Para $n \geq 16$ , $n \leq n /4$ , así que basta tomar $C \geq 4$ .

C \frac{n}{2} + C n + n \leq C n

Cota inferior

La recurrencia suma explícitamente $+ n$ , por lo que la cota inferior lineal es inmediata.

T (n) \geq n \Rightarrow T (n) \in Ω (n)

Conclusión

Como hay $O (n)$ y $Ω (n)$ , la cota es exacta.

T (n) \in Θ (n)

Ejemplo 2 — T(n)=2T(n/2)+n/log n

En cada nivel del árbol hay masa total $n$ , pero dividida por un logaritmo que cambia por nivel. La suma se comporta como una suma armónica sobre los logaritmos, por eso aparece $lo g lo g n$ .

Prueba guía de O(n log log n)

Suposición

La candidata viene de sumar costos por nivel.

T (n) \leq C n lo g lo g n

Hipótesis inductiva

Se usa con $k = n /2$ .

T (k) \leq C k lo g lo g k para k < n

Sustituir

El factor 2 cancela con el $n /2$ de cada subproblema.

T (n) \leq C n lo g lo g (n /2) + \frac{n}{lo g n}

Usar caída de log log

Para $n$ suficientemente grande existe una constante $α > 0$ que captura la disminución de $lo g lo g (n /2)$ .

lo g lo g (n /2) \leq lo g lo g n - \frac{α}{lo g n}

Cerrar

Basta elegir $C α \geq 1$ .

T (n) \leq C n lo g lo g n - \frac{C α n}{lo g n} + \frac{n}{lo g n} \leq C n lo g lo g n

Conclusión

La cota inferior se obtiene con una suma por niveles o una prueba Ω análoga.

T (n) \in O (n lo g lo g n)

No confundas log log con log

$2 T (n /2) + n$ da $n lo g n$ , pero $2 T (n /2) + n / lo g n$ reduce el costo de cada nivel y cae a $n lo g lo g n$ .

Ejemplo 3 — Hipótesis fortalecida

Para $T (n) = 2 T (n /2) + n / (lo g n)^{2}$ , el árbol sugiere $Θ (n)$ , porque la suma $\sum 1/ j^{2}$ converge.

Por qué la cota simple no cierra

Suposición simple

Parece natural porque esperamos una cota lineal.

T (n) \leq C n

Sustituir

Queda un término positivo extra.

T (n) \leq 2 C \frac{n}{2} + \frac{n}{( lo g n ) ^{2}} = C n + \frac{n}{( lo g n ) ^{2}}

No cierra

La cota es correcta, pero la hipótesis es demasiado débil.

C n + \frac{n}{( lo g n ) ^{2}} ≰ C n

Hipótesis fortalecida

Suposición fortalecida

El margen negativo está diseñado para absorber el término $n / (lo g n)^{2}$ .

T (n) \leq C n - D \frac{n}{lo g n}

Sustituir

El factor 2 cancela el tamaño $n /2$ .

T (n) \leq C n - D \frac{n}{lo g ( n /2 )} + \frac{n}{( lo g n ) ^{2}}

Cierre para n grande

Para $D$ suficientemente grande y $n \geq n_{0}$ , el margen negativo absorbe el término adicional.

- D \frac{n}{lo g ( n /2 )} + \frac{n}{( lo g n ) ^{2}} \leq - D \frac{n}{lo g n}

Resultado

La cota inferior $Ω (n)$ viene del costo acumulado de hojas o del árbol. Por tanto $T (n) \in Θ (n)$ .

T (n) \in O (n)

Ejemplo 4 — T(n)=T(n/2)+√n

La recurrencia $T (n) = T (n /2) + n$ tiene costos por nivel que decrecen geométricamente: $n, n /2, n /4, \dots$ . Por eso esperamos $Θ (n)$ .

Prueba de O(√n)

Suposición

El costo de la raíz domina la suma geométrica descendente.

T (n) \leq C n

Sustituir

Se aplica la hipótesis inductiva a $n /2$ .

T (n) \leq C n /2 + n

Factorizar

La meta es que el factor sea menor o igual a $C$ .

C n /2 + n = n (\frac{C}{2} + 1)

Cerrar

Basta elegir $C$ suficientemente grande.

\frac{C}{2} + 1 \leq C ⟺ C \geq \frac{1}{1 - 1/ 2}

Conclusión

La cota inferior $Ω (n)$ es inmediata porque la recurrencia suma $n$ .

T (n) \in Θ (n)

Ejemplo 5 — T(n)=T(n/3)+T(2n/3)+√n

Esta recurrencia no es balanceada y el Teorema Maestro básico no aplica. La intuición de árbol sugiere $Θ (n)$ : la suma de tamaños de las hojas mantiene masa lineal, mientras el término $n$ es sublineal.

Prueba guía de O(n)

Suposición fortalecida

La cota simple $T (n) \leq C n$ no cierra por el $+ n$ . Se agrega margen negativo.

T (n) \leq C n - D n

Sustituir

Se aplica la hipótesis a ambos subproblemas.

T (n) \leq C \frac{n}{3} - D n /3 + C \frac{2 n}{3} - D 2 n /3 + n

Agrupar

Se agrupan los términos lineales y los de raíz.

T (n) \leq C n - D n (\frac{1}{3} + \frac{2}{3}) + n

Cerrar con D grande

Como $\frac{1}{3} + \frac{2}{3} > 1$ , se puede elegir $D$ suficientemente grande.

D (\frac{1}{3} + \frac{2}{3} - 1) \geq 1 \Rightarrow T (n) \leq C n - D n

Conclusión

La cota inferior lineal se justifica por el aporte de hojas o por una cota Ω separada. Entonces $T (n) \in Θ (n)$ .

T (n) \in O (n)

Ejemplo 6 — T(n)=T(n/2)+T(n/4)+n

Esta recurrencia tiene dos subproblemas, pero la suma de tamaños es $n /2 + n /4 = 3 n /4$ . Por eso el costo local $+ n$ domina.

Prueba de Θ(n)

Suposición

La candidata es lineal.

T (n) \leq C n

Sustituir

Se acotan ambos llamados recursivos.

T (n) \leq C \frac{n}{2} + C \frac{n}{4} + n = \frac{3 C}{4} n + n

Cerrar

Basta elegir $C \geq 4$ .

\frac{3 C}{4} n + n \leq C n ⟺ C \geq 4

Cota inferior

El término local da la cota inferior.

T (n) \geq n \Rightarrow T (n) \in Ω (n)

Conclusión

La cota superior e inferior coinciden.

T (n) \in Θ (n)

Errores típicos

Errores frecuentes en sustitución

Error	Por qué está mal	Corrección
Decir $Θ$ sin probar $O$ y $Ω$	$Θ$ exige cota superior e inferior.	Probar ambas cotas o citar un método válido para una de ellas.
Usar la hipótesis con tamaños que no son menores que n	La inducción solo permite asumir la cota para subproblemas más pequeños.	Verificar que cada argumento recursivo sea menor que $n$ .
Ignorar casos base	La inducción necesita una base válida.	Ajustar $n_{0}$ y verificar los primeros valores necesarios.
Elegir una cota demasiado pequeña	La desigualdad no puede cerrar porque la cota candidata es falsa.	Volver al árbol o a la suma por niveles y corregir la suposición.
Rendirse cuando la cota simple no cierra	Puede hacer falta una hipótesis fortalecida.	Probar $T (n) \leq C g (n) - h (n)$ si el término residual lo exige.
Confundir prueba de O con solución exacta	Una cota superior no determina la función completa.	Reportar solo lo demostrado: $O$ , $Ω$ o $Θ$ .

Resumen operativo

Receta mínima

Proponer una cota candidata usando árbol, patrón conocido o método previo.
Traducir la cota a desigualdad con constantes.
Formular hipótesis inductiva para todo $k < n$ .
Sustituir la hipótesis en la recurrencia.
Simplificar hasta comparar contra la meta.
Elegir constantes y $n_{0}$ para cerrar la desigualdad.
Verificar casos base.
Concluir únicamente la cota que realmente se demostró.

Fórmulas clave

Cota superior

Esta es la forma que se prueba por inducción para $O$ .

T (n) \in O (g (n)) ⟺ \exists C > 0, \exists n_{0} : \forall n \geq n_{0}, T (n) \leq C g (n)

Cota inferior

Esta es la forma que se prueba para $Ω$ .

T (n) \in Ω (g (n)) ⟺ \exists c > 0, \exists n_{0} : \forall n \geq n_{0}, T (n) \geq c g (n)

Cota exacta

No se debe afirmar $Θ$ si solo se probó una dirección.

T (n) \in Θ (g (n)) ⟺ T (n) \in O (g (n)) \land T (n) \in Ω (g (n))

Hipótesis fortalecida

Se usa cuando $T (n) \leq C g (n)$ deja un término positivo que impide cerrar.

T (n) \leq C g (n) - h (n)