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
Fórum