Prova 1

Re: Prova 1

por Paulo Feofiloff -
Número de respostas: 0
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