MAC5710 Estruturas de Dados - Lista de exercícios 1

(baseados nos livros de Szwarcfiter & Markenzon e Ziviani)

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 a cota inferior deste problema é $\Omega(n \log n)$.

   (b) A cota inferior de um problema depende só do problema.

   (c) A cota inferior de um problema pode mudar com a descoberta de um novo algoritmo.

   (d) A cota superior depende somente do problema.

   (e) A cota superior é sempre não inferior à cota inferior.