Ata dos Exercícios (Semana 2-Crescimento de Funções)

3-2 Crescimentos assintóticos relativos

Indique, para cada par de expressões (A,B) na tabela a seguir, se A é O, o, Ômega, ômega ou Theta de B. Suponha que k >= 1, E > 0 e c > 1 são constantes. Sua resposta deve estar na forma de tabela, com "sim" ou "não" escrito em cada retângulo.

 

A

B

O

o

Õmega

ômega

Theta

a.

lgkn

ne

sim

sim

não

não

não

b.

nk

cn

sim

sim

não

não

não

c.

sqrt(n)

nsin n

-

-

-

-

-

d.

2n

2n/2

não

não

sim

sim

não

e.

nlg c

clg n

sim

não

sim

não

sim

f.

lg(n!)

lg(nn)

sim

não

sim

não

sim

3-3 Ordene as funções a seguir por ordem de crescimento; ou seja, encontre um arranjo g1, g2, ..., g9 das funções que satisfazem a g1 = Ômega(g2), g2 = Ômega(g3), ..., g8 = Ômega(g9).*

* OBS: Este não é o enunciado oficial do livro-texto. Porém, o Professor João Meidanis escolheu uma amostra de 9 das 30 funções contidas originalmente no enunciado. As funções escolhidas foram:

n2, n!, n3, lg2n, ln ln n, ln n, en, n, n lg n

Dentre as funções escolhidas acima, a solução correta é:

  1. n!

  2. en

  3. n3

  4. n2

  5. n lg n

  6. n

  7. lg2n

  8. ln n

  9. ln ln n

3-4 Propriedades da notação assintótica

Sejam f(n) e g(n) funções assintoticamente positivas. Prove ou conteste cada uma das seguintes conjecturas.

  1. f(n) = O(g(n)) implica g(n) = O(f(n)). F

  2. f(n) + g(n) = Theta(min (f(n), g(n))). F (seria V se trocar min por max)

  3. f(n) = O(g(n)) implica lg(f(n)) = O(lg(g(n))), onde lg(g(n)) > 1 e f(n) >= 1 para todo n suficientemente grande. V (as condições são para evitar problemas se f e g são constantes)

  4. f(n) = O(g(n)) implica 2f(n) = O(2g(n)). V

  5. f(n) = O(f(n)2). F (falha quando f(n) está entre 0 e 1)

  6. f(n) = O(g(n)) implica g(n) = Ômega(f(n)). V

  7. f(n) = Theta(f(n/2)). F (contra-exemplo: 2n e 2n/2)

  8. f(n) + o(f(n)) = Theta(f(n)). V

Autor: Eduardo Akira Yonekura

RA: 025989