AAED - Lista de exercícios 1

Prévia do material em texto

Pós-Graduação em Ciência da Computação Universidade Federal de São Paulo - São José dos Campos
Exerćıcios sobre Notação Assintótica
AAED — Análise de Algoritmos e Estruturas de Dados
Prof. Jurandy G. Almeida Jr.
1o Semestre de 2020
Exerćıcios
1. Prove que n2 + 10n+ 20 ∈ O(n2).
2. Prove que 300 ∈ O(1).
3. Prove que dn/3e ∈ O(n). É verdade que n ∈ O(bn/3c)?
4. Prove que lg n ∈ O(log10 n).
5. Prove que n ∈ O(2n).
6. Prove que lg n ∈ O(n).
7. Prove que n/1000 não é O(1).
8. Prove que 12n
2 não é O(n).
9. Suponha T definida para n = 0, 1, . . .
(a) Se T (n) ∈ O(1), mostre que existe c′ tal que T (n) ≤ c′ para todo n ≥ 0.
(b) Se T (n) ∈ O(n), mostre que existe c′ tal que T (n) ≤ c′ n para todo n ≥ 1.
10. Prove que n2 + 999n+ 9999 ∈ O(n2).
11. Prove que 12n(n+ 1) ∈ O(n
2).
12. É verdade que 1100n
2 − 999n− 9999 ∈ O(n)? Justifique.
13. Suponha que f(n) = n2 quando n é par e f(n) = n3 quando n é ı́mpar.
(a) É verdade que f(n) = O(n2)?
(b) É verdade que f(n) = O(n3)?
(c) É verdade que n2 = O(f(n))?
(d) É verdade que n3 = O(f(n))?
14. É verdade que n2 = O(2n)?
15. É verdade que lg n = O(
√
n)?
16. Suponha f(n) = 64n lg n e g(n) = 8n2, com n inteiro positivo. Para que valores de n temos
f(n) ≤ g(n)?
17. Suponha T e f definidas para n = 1, 2, . . . Mostre que se T (n) = O(f(n)) e f(n) > 0 para
n ≥ 1 então existe c′ tal que T (n) ≤ c′ f(n) para todo n ≥ 1.
18. Faz sentido dizer “T (n) = O(n2) para n ≥ 3”?
19. É verdade que 2n = O(n)?
É verdade que n = O(lg n)?
Justifique.
20. É verdade que n+
√
n é O(n)?
É verdade que n é O(
√
n)?
É verdade que n2/3 é O(
√
n)?
É verdade que
√
n+ 1000 é O(n)?
21. É verdade que lg n = O(n1/2)?
É verdade que
√
n = O(lg n)?
É verdade que lg n = O(n1/3)?
Justifique. (Sugestão: prove, por indução, que lg x ≤ x para todo número real x ≥ 1.)
22. É verdade que dlg ne = O(lg n)?
23. Interprete e prove a afirmação O(n2) +O(n2) +O(n2) = O(3n2).
24. Interprete e prove a afirmação nO(n) = O(n2).
25. Interprete e prove a afirmação O(3n2 + 4n) = O(n2).
26. (Propriedade Transitiva)
Suponha T (n) = O(f(n)) e f(n) = O(g(n)).
Mostre que T (n) = O(g(n)).
Dê um exemplo interessante.
27. (Regra da Soma, Caso Especial)
Suponha que T (n) = O(f(n)) e mostre que T (n) + f(n) = O(f(n)).
Dê um exemplo interessante.
28. (Regra da Soma, Caso Geral)
Suponha que T1(n) = O(f1(n)) e T2 = O(f2(n)).
Se f1(n) = O(f2(n)), mostre que T1(n) + T2(n) = O(f2(n)).
29. O que significa “T (n) = n2 +O(n)”?
Mostre que se T (n) = n2 +O(n) então T (n) = O(n2).
30. O que significa “T (n) = nO(lg n)”?
Mostre que T (n) = nO(lg n) se, e somente se, T (n) = O(n lg n).
31. Interprete e prove a afirmação 7 ·O(n) = O(n).
32. Interprete e prove a afirmação O(n) +O(n) = O(n).
33. Prove que O(n) = O(n2). É verdade que O(n2) = O(n)?
34. Interprete e prove a afirmação (n+ 2) ·O(1) = O(n).
35. Interprete e prove a afirmação O(1) + · · ·+O(1)︸ ︷︷ ︸
n+2
= O(n).
36. Prove que O(1) +O(1) +O(1) = O(1).
É verdade que O(1) = O(1) +O(1) +O(1)?
37. Interprete e prove a afirmação O(f) +O(g) = O(f + g).
38. Prove que n2 + 10n+ 20 = Ω(n2).
Prove que n2 − 10n− 20 = Θ(n2).
39. Prove que n = Ω(lg n).
40. Prove que lg n = Θ(log10 n).
41. Prove que 0.0001n3 − 100n2 − 100n+ 3 = Θ(n3).
42. Prove que 3n log10 n+ log10 n
10 = Θ(n log10 n).
43. É verdade que 2n = Ω(3n)?
44. É verdade que 2n3 + 5
√
n = Θ(n3)?
45. Prove que f(n) = 12 + 22 + · · ·+ n2 é igual n3/3 +O(n2).
46. Prove que
∑n
i=1dlg ie = Θ(n lg n).
47. Mostre que as seguintes relações são válidas usando a definição de constantes:
(a) 103n2 + 106n ∈ Θ(n2);
(b) 11n2 − 106n ∈ Ω(n2);
(c) n ∈ o(n3/2);
(d) n ∈ ω(n9/10).
48. Mostre que as seguintes relações são válidas:
(a) n log n ∈ ω(n);
(b) log2 n ∈ o(n);
(c) log5 n ∈ o(n1/2);
(d) logd n ∈ o(n�), onde d ∈ N∗ e 0 < � < 1;
(e) adn
d + ad−1n
d−1 + . . . + a1n + a0 ∈ Θ(nd), onde d ∈ N∗ e ai é constante para todo
0 ≤ i ≤ d;
(f) nd ∈ o(2n), onde d ∈ N∗;
49. Dadas duas funções positivas f(n) e g(n). Diz-se que f(n) = Θ(g(n)) se f(n) = O(g(n)) e
g(n) = O(f(n)). Mostre que max(f(n), g(n)) = Θ(f(n) + g(n)).
50. Indique para cada par de expressões (A,B) na tabela abaixo, se A é O, o, Ω, ω, ou Θ de B.
Assuma que k ≥ 1, � > 0 e c > 1 são constantes. Sua resposta deve ser na forma sim ou não
acompanhada da justificativa.
A B O o Ω ω Θ
(a) lgk n n�
(b) nk cn
(c)
√
n nsinn
(d) 2n 2n/2
(e) nlgm mlgn
(f) lg (n!) lg (nn)
51. Suponha que os algoritmos A e B só dependem de um parâmetro n. Suponha ainda que A
consome S(n) unidades de tempo enquanto B consome T (n) unidades de tempo. Quero provar
que o algoritmo A é pelo menos tão eficiente quanto o algoritmo B (no sentido assintótico).
Devo mostrar que existe f(n) tal que
S(n) = O(f(n)) e T (n) = O(f(n))?
S(n) = O(f(n)) e T (n) = Ω(f(n))?
S(n) = Ω(f(n)) e T (n) = O(f(n))?
S(n) = Ω(f(n)) e T (n) = Ω(f(n))?
Que devo fazer para mostrar que A é mais eficiente que B?
52. Demonstre as seguintes propriedades:
(a) Se f(n) ∈ Ω(g(n)) e g(n) ∈ Ω(h(n)), então f(n) ∈ Ω(h(n)).
(b) Se f(n) ∈ O(g(n)) e g(n) ∈ O(h(n)), então f(n) ∈ O(h(n)).
(c) Se f(n) ∈ ω(g(n)) e g(n) ∈ ω(h(n)), então f(n) ∈ ω(h(n)).
(d) Se f(n) ∈ o(g(n)) e g(n) ∈ o(h(n)), então f(n) ∈ o(h(n)).
(e) f(n) ∈ Θ(g(n)) se, e somente se, g(n) ∈ Θ(f(n)).
(f) f(n) ∈ O(g(n)) se, e somente se, g(n) ∈ Ω(f(n)).
(g) Se f(n) ∈ Θ(g(n)) e g(n) ∈ O(h(n)), então h(n) ∈ Ω(f(n)).
(h) Se f(n) ∈ Θ(g(n)) e g(n) ∈ Ω(h(n)), então h(n) ∈ O(f(n)).