Hola y gracias por tomarse el tiempo de responder a mi pregunta.
La cuestión es realmente el propio título. Estamos estudiando cómo resolver recurrencias utilizando el método de sustitución e inducción. ¿Cómo puedo demostrar que esto es correcto?
Me gustaría que razonaran los conceptos en lugar de limitarse a dar una solución.
¡Muchas gracias!
El método más básico consiste en ampliar la fórmula. Rara vez funciona, pero es lo suficientemente simple como para que valga la pena comprobarlo antes de proceder a cosas más complicadas.
\begin{align} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &\vdots \\ &= T(0) + 1 + 2 + \ldots + (n-2) + (n-1) + n \\ &= T(0) + \frac{n(n+1)}{2} = O(n^2) \end{align}
¡Salud!
EDITAR: Se ha añadido la falta de $T(0) = O(1)$ término (gracias a Hurkyl).
¡Esto es genial gracias dtldarek! Aceptaré tu respuesta como correcta en cuanto transcurra el tiempo mínimo requerido. ¿Cómo determinarías el límite inferior de la misma ecuación?
@Peter En realidad se trata de un conjunto de igualdades, por lo que funcionan en ambos sentidos. De hecho $T(0) + \frac{n(n+1)}{2} = \Theta(n^2)$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
¿Busca simplemente probar la afirmación, o se pregunta cómo la descubriría si no se la dieran? ¿Qué sucede, por cierto, cuando intentas el método de sustitución o inducción?