Analise e complexidade de algoritmos

Analise e complexidade de algoritmos

5) O que significa dizer que uma função g(n) é O(f(n))?
Uma função f (n) domina assintoticamente outra função g(n) se existem duas constantes positivas c e m tais que, para n ≥ m, temos |g(n)| ≤ c x |f(n)|.

6) Indique se as afirmativas a seguir são verdadeiras ou falsas e justifique a sua resposta:
a. 2n+1 = O(2n).
b. 22n = O(2n).
c. É melhor um algoritmo que requer 2n passos do que um que requer 10n5 passos.
d. f(n) = O(u(n)) e g(n) = O(v(n)) => f(n) + g(n) = O(u(n) + v(n))
e. f(n) = O(u(n)) e g(n) = O(v(n)) => f(n) - g(n) = O(u(n) - v(n))

A=Verdadeira
B=Verdadeira
C=Verdadeiro, o melhor é o 2n; porque quanto maior o numero que multiplica o “n” maior o tempo de execução do programa.
D= Verdadeira
E=Falsa. se f(n) – g(n) = O(u(n)) – O(v(n)) = O(u(n))+(-1)O(v(n)); como -1 é uma constante, ela pode ser desconsiderada, de acordo com as propriedades da notação O.

7) Suponha um algoritmo A e um algoritmo B com funções de complexidade de tempo a(n) = n2 – n +549 e b(n) = 49n + 49, respectivamente. Determine quais são os valores de n pertencentes ao conjunto dos números naturais para os quais A leva menos tempo para executar do que B.

Não existem valores de “n” que satisfaça essa condição.

8) Considere que você tenha um problema para resolver e duas opções de algoritmos. O primeiro algoritmo é quadrático tanto no pior caso quanto no melhor caso. Já o segundo algoritmo, é linear no melhor caso e cúbico no pior caso. Considerando que o melhor caso ocorre 90% das vezes que você executa o programa enquanto o pior caso ocorre apenas 10% das vezes, qual algoritmo você escolheria? Justifique a sua resposta em função do tamanho da