From tachard@ic.unicamp.br Wed Mar 10 09:55:40 2010
Date: Wed, 10 Mar 2010 09:55:40 -0300
From: Alexandre Passos <tachard@ic.unicamp.br>
Reply-To: mo417_2010s1@googlegroups.com
To: mo417_2010s1@googlegroups.com
Subject: Ata da questão 3-4

a) As funcoes n e n^2 servem como contra-exemplo.
b) Idem
c) Basta substituir na definicao que, se f(n) <= c g(n) para n > n0,
log(f(n)) <= c' log(g(n)), onde c' = 1 + lg(1 + c), para o mesmo n > n0.
d) 2n e n servem como contra-exemplo
e) 1/n serve como contra-exemplo
f) pela regra do transposto simetrico do livro isto segue imediatamente
g) 2^n serve como contra-exemplo
h) Pela propriedade de que f(n) + g(n) = Theta(max(f(n),g(n))) isto
segue imediatamente.

--
 - Alexandre