59
Algoritmos - Teoria e Prática - 3ª Ed. 2012

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 4keyboard_arrow_downkeyboard_arrow_up

Consideremos . Através do método da substituição, podemos provar que mostrando que para todo .

Passo 2 de 4keyboard_arrow_downkeyboard_arrow_up

O caso base é . Então existe uma constante positiva 1 tal que onde . Mostramos então para :

Passo 3 de 4keyboard_arrow_downkeyboard_arrow_up

Usamos o somatório de série geométrica nesse caso, :

Passo 4 de 4keyboard_arrow_downkeyboard_arrow_up

Portanto, provamos que decorre de e da condição inicial .

Navegar por capítulo