Lista de exercicio 3 Analise e Projeto de Algoritmos

Aluno: Vinicius Barcelos Silva
Matricula: 108251
Lista 3 3.1­3
Primeiro vamos definir a função max ( f(n), g(n)), vamos definir a função h(n) = max ( f(n), g(n)).
Agora:
h(n) = { f(n) se f(n) ≥ g(n) h(n) = { g(n) se f(n) < g(n) Tendo que f(n) e g(n) são assintoticamente positivos, existe um n0 tal que f(n) ≥ 0 e g(n) ≥ 0 para todo n ≥ n0 .
Assim, para todo n ≥ n0 , f(n) + g(n) ≥ f(n) ≥ 0 e f(n) + g(n) ≥ g(n) ≥ 0.
Uma vez que para qualquer n particular, h(n) é f(n) ou g(n), logo temos que f(n) + g(n) ≥ h(n) ≥ 0, com isso mostramos que h(n) = max ( f(n), g(n)) ≤ c2( f(n) + g(n)) para todo n ≥ n0 . Tendo c2 =
1 na definição de Θ. Da mesma maneira temos que para qualquer n particular, h(n) é maior que f(n) e g(n), tendo para todo n ≥ n0 , 0 ≤ f(n) ≤ h(n) e o 0 ≤ g(n) ≤ h(n). Com a adição destes dois diferentes, produzimos 0 ≤ f(n) + g(n) < 2h (n), equivalente à 0 <= ( f(n) + g(n)) / 2 ≤ h(n), que mostramos que h(n) = max ( f(n), g(n)) ≥ c1( f(n) + g(n)) para todo n ≥ n0 . Tendo c1 = 1/2 na definição de
Θ.

3.1­4
2n+1 = O (2^2n) mas 2^2n =/ O(2^n).
Temos que mostrar que 2n+1 = O (2^2n) , agora temos que encontrar uma constante c, n0 > 0 tal que 0 ≤ 2^(n+1) ≤ c • 2^n para todo n ≥ n0 .
Desde que 2^(n+1) = 2 • 2^2n para todo n, podemos assim satisfazer a definição com c = 2 e n0
= 1.
Assim mostramos que 2^2n =/ O(2^n) , assumindo que existem constantes c , n0 > 0 tal que
0 ≤ 2^n ≤ c • 2^n para todo n ≥ n0 .
Portanto, 2^2n = 2^n • 2^n ≤ c • 2^n ⇒ 2^n ≤ c . Mas a constante não é maior que todos os 2^n , assim provamos por contradição que a hipótese não é verdadeira. 3.1­7
Temos que: o: limite superior que não é assintoticamente restrito ω: limite inferior que não é assintoticamente restrito
Se o limite “o” tentendo para o infinito é igual a 0 e o limite “ω” tentendo para o infinito é igual ao infinito, temos que a intersecção de o(g(n)) com ω(g(n)) é vazia.

3.2­3
(I) Para o(g(n)) = (f(n) : para qualquer constante c > 0,