Publiquei os gabaritos das tarefas 7 e 8.
Se você não sabe onde errou, venha falar comigo.
Publiquei as notas da tarefa 8.
Se você não sabe onde errou, venha falar comigo.
Se você não sabe onde errou, venha falar comigo.
| T(n) | = | 3 T(n/2) + n |
| ≥ | 3 (n/2)lg 3 + n |
Por hipótese de indução,
T(n/2) >= (n/2)^{lg 3}.
T(n/2) >= (n/2)^{lg 3}.
Eu também tinha a mesma dúvida. Mas a hipótese de indução não está trocada? T(n/2) >= (n/2)^{lg 3}.
Posso estar errado,
mas não estou enxergando o meu erro...
Onde a hipótese de indução está errada?
mas não estou enxergando o meu erro...
Onde a hipótese de indução está errada?
Opa, percebi meu engano. Tava confundindo os dois sabores da demonstração.
"Dois sabores"?
Você está se referindo a O versus Omega?
É isso?
Você está se referindo a O versus Omega?
É isso?
Publiquei as notas da tarefa 7.