MAC 5711 — Análise de Algoritmos Lista 1 — 14/3/2001

Obs.: em tudo o que se refere a comparar crescimento de funções, supõe-se que as funções dadas são assintoticamente positivas (só têm valores positivos a partir de algum ponto).

Exercícios entregues para correção serão corrigidos na medida do possível. Esta lista não entrará para a média final; assim faça e entregue quantos quiser.

1. Prove:

(a) max(f(n), g(n)) = Θ(f(m) + g(n)).

(b) ∑_{i=1}^{n} Θ(1) = Θ(n).

2. A função lg^{∗} n, conhecida como “log estrela”, é definida por:

lg ∗n = min {i ≥ 0 : lg^{(i)} n ≤ 1}

onde lg^{(i)} n é lg iterada i vezes:

lg^{(i)} n = \{ \begin{matrix}n & if i = 0. \\ lg(lg^{(i−1)} n) & if i > 0 and lg^{(i−1)} n > 0. \\ indefinido & em outros casos. \end{matrix}

Qual o menor valor de n tal que lg^{∗} n = 5?

3. Classifique essas funções por ordem de crescimento, ou seja, coloque-as numa ordem g_{1}, g_{2}, …, g_{25} de forma que g_{i+1} = Ω(g_{i}), para cada i. Indique também os casos em que g_{i+1} = Θ(g_{i}).

(3/2)^{n} (\sqrt{2})^{lg n} lg^{∗} n  n^{2}  (lg n)!
n^{3}  lg^{2} n lg(n!) 2^{2^{n}} n^{1/ lg n}
lg lg n n2^{n} n^{lg lg n} ln n 2^{n}
2^{ln n} (lg n)^{lg n} 4^{lg n} (n + 1)! \sqrt{lg n}
n!  2^{\sqrt{2 lg n}}  n  n lg n  1

4. Mostre que:

(a) Se g(n) = o(f(n)), então f(n) + g(n) = Θ(f(n)). O que acontece com essa soma se só se sabe que g(n) = O(f(n))?

(b) Se f_{i}(n) = O(g_{i}(n)), i = 1, 2, então f_{1}(n)f_{2}(n) = O(g_{1}(n)g_{2}(n)).

5. Mostre que se f(n) é um polinômio (assintoticamente positivo) de grau k, então:

(a) f(n) = Θ(n^{k}).

(b) Se ε > 0, então f(n) = o(n^{k+ε}).

6. Prove ou desprove:

(a) f(n) = O(g(n)) implica g(n) = O(f(n)).

(b) f(n) + g(n) = Θ(min(f(n), g(n))

(c) Se f(n), g(n) > 1 para todo n suficientemente grande, e f(n) = O(g(n)), então lg(f(n)) = O(lg(g(n))) .

(d) f(n) = O(g(n)) implica 2^{f(n)} = O(2^{g(n)}) .

(e) f(n) = O(f(n)^{2}) .

(f) f(n) = O(g(n)) implica g(n) = Ω(f(n)) .

(g) f(n) = O(f(n/2))

7. A função ⌈lg n⌉! é limitada polinomialmente? E a função ⌈lg lg n⌉! ?