Algumas pessoas tiveram dificuldade de resolver o seguinte exercício
do caderno de exercícios opcionais (é o exercício Exr 6.13 na versão
atual do caderno):
Considere a função T definida pela seguinte recorrência sobre os
racionais positivos:
T(r) = 1 se 0 < r <= 1
T(r) = T(r/3) + T(2r/3) + 5r se r > 1.
Infelizmente, essa recorrência está torta (eu errei...) pois o
intervalo entre 0 e 1/3 em nada contribui para definir T e atrapalha
a solução. Faz muito mais sentido usar a seguinte definição:
Considere a função T definida pela seguinte recorrência sobre os
racionais maiores que 1/3:
T(r) = 1 se 1/3 < r <= 1
T(r) = T(r/3) + T(2r/3) + 5r se r > 1.
Queremos mostrar que T(r) = O(r lg(r)). Para isso, vamos mostrar que
T(r) < 90r lg(r) + lg(r) + 60
para todo racional r > 1/3.
Prova, por indução em r:
Como vamos precisar de lg(3), observe desde já que 1.58 < lg(3) < 1.59.
Para começar, tome um racional r tal que 1/3 < r <= 1. Então
90 r lg(r) + lg(r) + 60 > 90 (1/3) lg(1/3) + lg(1/3) + 60
= -30 lg(3) - lg(3) + 60
= -31 lg(3) + 60
> -50 + 60
> 1
= T(r).
Isto conclui a base da indução. Suponha agora que r > 1. Então, por
hipótese de indução, temos
T(r) = T(r/3) + T(2r/3) + 5r
< 90(r/3)lg(r/3) + lg(r/3) + 60 + 90(2r/3)lg(2r/3) + lg(2r/3) + 60 + 5r
= 30r lg(r/3) + lg(r/3) + 60 + 60r lg(2r/3) + lg(2r/3) + 60 + 5r
= 30r lg(r/3) + lg(r/3) + 60 + 60r(lg(r/3)+lg(2)) + lg(r/3)+lg(2) + 60 + 5r
= 30r lg(r/3) + lg(r/3) + 60 + 60r lg(r/3) + 60r + lg(r/3) + 1 + 60 + 5r
= 30r lg(r/3) + 60r lg(r/3) + lg(r/3) + 60 + 60r + lg(r/3) + 61 + 5r
= 90r lg(r/3) + lg(r/3) + 60 + 65r + lg(r/3) + 61
= 90r (lg(r)-lg(3)) + lg(r)-lg(3) + 60 + 65r + lg(r)-lg(3) + 61
= 90r lg(r) + lg(r) + 60 - 90 lg(3) r + 65r + lg(r) - 2lg(3) + 61
< 90r lg(r) + lg(r) + 60 - 142r + 65r + lg(r) - 3 + 61
= 90r lg(r) + lg(r) + 60 - 77r + lg(r) + 58
< 90r lg(r) + lg(r) + 60 - 77r + r + 58
= 90r lg(r) + lg(r) + 60 - 76r + 58
< 90r lg(r) + lg(r) + 60.
Fim da prova.
Fórum