algoritimos

Algoritmos - Exercícios
1) O que significa dizer que uma função g(n) é O(f(n))?
Que apartir de determinado tempo a função G(n) nunca alcansará a F(n)
2) O que significa dizer que um algoritmo executa em tempo proporcional a n?
Significa dizer que quanto maior o n, maior é o tempo de execução.
3) Explique a diferença entre O(1) e O(2).
Nenhuma pois ambos são constantes
4) Qual algoritmo é melhor: um algoritmo que requer n^5 passos ou um que requer 2^n Passos?
N^5, pois apesar de no inicio pareça não ser, apartir de determinado ponto (apartir do 22) ele fica exponencialmente melhor
5) Indique se as afirmativas a seguir são verdadeiras ou falsas e justifique sua resposta:
a) 2^n+1=O(2n)  Sim, pois o 1 é insignificante;
b) 2^2n=O(2^n)  Não, pois dobra o valor do n;
6) Suponha um algoritmo A e um algoritmo B com funções de complexidade 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.
7) Qual é a ordem de complexidade das seguintes funções (utilize a notação O).
a) f(n) = n2+ 2 O(n^2)
b) g(n) = 503 ) 0(1)
c) g(n) = 2 log n + n 0(n)
d) g(n) = 10. 2n 0(2^n)
e) f(n) = n log n + log n 0(n log n)
8) Qual dessas funções possui a maior ordem de complexidade?
2^n
9) Arranje as seguintes expressões de acordo com a taxa de crescimento (da menor para a maior): 4n2, n!, log3n, 3n, 20n, 2, log2n.

10) Analise a complexidade dos seguintes trechos de códigos:
For