MO417 - Ata de exercícios resolvidos em aula

Aula de 24/03/2009, 3a feira

Livro: Algoritmos, Teoria e Prática - Tradução da 2a edição americana
Capítulo 3 - Crescimento de Funções

Problema 3-3:

a. Ordene as funções a seguir por ordem de crescimento; ou seja, encontre um arranjo
g1,g2,...,g30 das funções que satisfazem a g1=Ω(g2),g2=Ω(g3),...,g29=Ω(g30).
Particione sua lista em classes de equivalência tais que f(n) e g(n) estejam na mesma
classe se e somente se f(n) = θ(g(n))

Resolução:

	22n+1 		≥ 	22n		≥	(n + 1)!		≥	n!		≥	en		≥	 n.2n		≥

	
	2n		≥	(3/2)n		≥	lg n lg n		=	nlg lg n	≥	(lg n)!		≥	n3		≥

	
	4lg n 		=	n2		≥	n lg n			=	lg (n!)		≥	n		=	2lg n		≥	

				 
	(√2)lg n	≥	2√2 lg n	≥	lg2n			≥	ln n		≥	√lg n		≥	ln ln n		≥	

	
	2lg* n 		≥	lg* n		=	lg*(lg n)		≥	lg(lg* n)	≥	n1/lg n		=	1

b. Dê um exemplo de uma única função não negativa f(n) tal que, para todas as funções gi(n) da parte (a),
f(n) não seja nem O(gi(n)) nem Ω(gi(n)).

Resolução:
		f(n) = { 22n+2 	se n é impar 
			 0 	se n é par
[Redator: Fernando José Vieira da Silva (RA: 085324)]