Como eu provo que vale a relação de recorrência da questão 2? Surgiu-me essa dúvida com relação às recorrências. (depois de ter lido errado o enunciado do exercício 2 e ter gasto um tempo exponencial tentando inutilmente provar que a recorrência vale)
Existe algum truque para fazer sumir os pisos e tetos nesses casos?
Acho que está havendo alguma confusão.
A questão 2 não pedia prova de que
"vale a relação de recorrência".
A relação de recorrência é DADA.
Eu queria, isto sim, que você provasse
que a função definida pela recorrência
é <= 10 n lg n.
(Não sei se você já olhou o meu gabarito.)
Felizmente, lidar com o teto de (n-1)/2
é fácil:
teto((n-1)/2)
<= (n-1)/2 + 1/2
<= n/2
Como eu provo que vale a relação de recorrência da questão 2
A questão 2 não pedia prova de que
"vale a relação de recorrência".
A relação de recorrência é DADA.
Eu queria, isto sim, que você provasse
que a função definida pela recorrência
é <= 10 n lg n.
(Não sei se você já olhou o meu gabarito.)
Felizmente, lidar com o teto de (n-1)/2
é fácil:
teto((n-1)/2)
<= (n-1)/2 + 1/2
<= n/2
Como eu provo que vale a relação de recorrência da questão 2