Lista_de_Exercicios I Complexidade

Lista #1

1) Se possível, mostre que:
a) n+ log n + 100 é O(n)
2
n
b) 2 é O(n)
c) 2n + n . log n é O(n)
2
2n n d) 2 é O(2 ) n+1 n
e) 2 é O(2 )

2) Se possível, mostre que g(n) é limite inferior para f(n):
a) f(n) = 5n e g(n) = log n
2
b) f(n) = log n +10 e g(n) = n
2
c) f(n) = 2n³ e g(n) = n²
d) f(n) = n²+4 e g(n) = n³
d) f(n) = 2

2n

e g(n) = 2

n

3) Para cada uma das notações O, Θ, Ω, mostre ou conteste a validade das seguintes propriedades: transitividade, reflexividade e simetria.
Por exemplo, para transitividade mostre ou conteste por contraexemplo que
O(f)=O(g) e O(g)=O(h) implica que O(f)=O(h)

4) Sejam f(n) e g(n) funções assintoticamente não negativas. Usando a definição de notação Θ, mostre que max ( f(n), g(n) ) = Θ ( f(n)+g(n) )
5) Prove que 2n³ ≠ Θ(n²).
6) Mostre que, para quaisquer constantes reais a e b, onde b>0, (n+a)b=Θ(nb).

7) Responda com V ou F, corrigindo as sentenças incorretas.
a) Para duas funções g(n) e f(n), f(n) = Θ(g(n)), se e somente se: f(n) = O(g(n)) e f(n)=Ω(g(n)). n b) Se T(x) é um polinômio de grau n então: T(x) = Θ(x ).
c) Se f(n) for um polinômio de grau d então f(n) = O(d).
d) A indexação de um vetor leva o mesmo tempo seja qual for o índice que se queira buscar, portanto é uma operação de complexidade constante Ω(1).
e) Se T1(n) = O(f(n)) e T2(n) = O(g(n)) então T1(n) x T2(n) = O(f(n) + g(n)).

8) Determinar a expressão da complexidade média de uma busca sequencial não ordenada, com n chaves, supondo que a probabilidade de busca de qualquer chave, exceto a última, é igual à metade da probabilidade de busca da chave seguinte. Supor também que a probabilidade de a chave procurada se encontrar na lista é igual a q.

9) Determinar a expressão da complexidade média de uma busca sequencial não ordenada, com n chaves, supondo que a probabilidade de busca de qualquer chave, exceto a última, é igual à um terço da probabilidade de busca da chave seguinte. Supor também que a probabilidade de a chave procurada se encontrar na lista é