2.3.4. Otras técnicas.
Se usa cuando las ecuaciones son no lineales y no se puede aplicar ninguna de las técnicas anteriores.
Inducción: Dado t(n), suponer que pertenece a algún orden O(f(n)) y demostrarlo por inducción.
- Para algún valor pequeño, t(n) ? c1·f(n)
- Suponiendo que t(n-1) ? c1·f(n-1), entonces se demuestra que t(n) ? c1·f(n)
Ejemplo. Dado lo siguiente,demostrar que t(n)??(n!):
t(n) = b·n2 + n·t(n - 1)
- Demostrar por inducción que t(n) ? ?(n!).
- Demostrar por inducción que t(n) ? O(n!).