Lista de exercicios (ED)

Prévia do material em texto

Lista de exerc´ıcios
Luiz Alberto
26 de agosto de 2016
Das 6 questo˜es dessa lista, 3 sera˜o usadas para a elaborac¸a˜o do 1o teste.
Questa˜o 1
Sejam f(n) = 2n, g(n) = 3n e h(n) = f(n)g(n). Prove que h(n) ∈ θ(n2).
Questa˜o 2
Seja f(n) = 22n. E´ verdade que f(n) ∈ O(2n)? Justifique sua resposta.
Questa˜o 3
Dada uma constante a ∈ R, prove que (x+ a)2 ∈ θ(x2).
Questa˜o 4
E´ verdade que cos(x) ∈ θ(1)? Justifique sua resposta.
Questa˜o 5
Prove que O e´ transitiva.
Questa˜o 6
Quantas operac¸o˜es de soma o seguinte algoritmo faz? Elabore uma func¸a˜o
que relacione a entrada com o nu´mero de operac¸o˜es de soma. Deˆ a essa func¸a˜o
um limite assinto´tico superior va´lido.
Input: n ∈ N.
1 soma = 0
2 for i in 1, 2, . . . , n do
3 soma = soma + i + 2
4 end
Result: soma
1