MAC 5741 - Introdução a Algoritmos e Arquiteturas Paralelas
Lista de exercícios 1

(baseados nos livros de Szwarcfiter, J. L. e Markenzon, L. Estruturas de Dados e seus Algoritmos. LTC Editora, 1994 e Ziviani, N. Projeto de Algoritmos com Implementações em Pascal e C. Livraria Pioneira Editora, 1993.)

1. Escrever as seguintes funções em notação $O$:

   (a) $3 n^3 + 20 n^2 \log n$

   (b) $3 n^n + 5 . 2^n$

   (c) $(n-1)^n + n^{(n-1)}$

   (d) $4 n + 2 n \log n$

   (e) 34

2. O que significa dizer que a função $g(n)$ é $\Omega(h(n))$? Dê a definição formal.

3. Indique se as afirmativas abaixo são verdadeiras ou falsas e justifique sucintamente sua resposta.

   (a) $2^{(n+1)} = O(2^n)$

   (b) $2^{2n} = O(2^n)$

4. Responder se é certo ou errado:

   (a) Para um dado problema, se a complexidade do melhor caso de um algoritmo é $O(n \log n)$, então o limite inferior deste problema é $\Omega(n \log n)$.

   (b) O limite inferior de um problema depende só do problema.

   (c) O limite inferior de um problema pode mudar com a descoberta de um novo algoritmo.

   (d) O limite superior depende somente do problema.

   (e) O limite superior é sempre não inferior ao limite inferior.