Lista de exercicio 5 Analise e Projeto de Algoritmos

Aluno: Vinicius Barcelos Silva
Matricula: 108251
Lista 5 ­ APA

4.1­1 (para esse exercício temos que [ ] representará o limite superior)
Substituindo na expressão temos que T (n) ≤ c lg(n − b) . Assumindo para [n/2], teremos que:
T (n) ≤ c lg([n/2 − b]) + 1 < c lg(n/2 − b + 1) + 1 = c lg(n−2b+2
2 )+1 = c lg(n − 2b + 2) − c lg2 + 1 ≤ c lg(n − b)

No ultimo passo temos que necessariamente ter b ≥ 2 e c ≥ 1 . 4.1­6
Alterando as variaveis de modo que m = lg n ⇒ n = 2m a recorrencia se torna
T (2m) = 2T (2m/2) + 1 .
Agora S(m) = T (2m) e vamos escrever a recorrencia como S(m) = 2S(m/2) + 1 , sendo sua solução S(m) = O(lg m) .
Voltando, nós teremos T (n) = (2m) = S(m) = O(lg m) = O(lg lg n) . 4.2­3 (para esse exercício temos que [ ] representará o limite inferior) cn (1) cn/2 cn/2 cn/2 cn/2 (2) cn/4 cn/4 cn/4 cn/4
(3)

(1) cn
(2) 2cn
(3) 4cn O total do somatório vai ser: lg n

T (n) = cn ∑ 2i = cn(21+lg n − 1) = cn(2n − 1) = 2cn2 − cn = O(n2) i=0 4.2­4

A arvore terminara com n = 1, que acontece quando n­ka=1, isto é, k=(n­1)/a k = (n − 1)/a ≈ n/a niveis.
A soma total de T (n) = O(n2) , isto é, onde T (n) < dn2 .
Supondo que T (k) < dk2 para todo k < n , então mostraremos que k = n :
T (n) = T (n − a) + T (a) + cn
< d(n − a)2 + da2 + cn
= dn2 − 2adn + 2da2 + cn
= dn2 − (2adn − 2da2 − cn)
A ordem de (2adn − 2da2 − cn) é maior que 0, logo podemos escolher por exemplo d = (c + 1)/2a , nesse caso teremos que T (n) < dn2 − (n − ac − a) , que será menor que dn2 para grandes valores de n, isto é, T (n) = O(n2) .

4.3­1
i) T(n) = 4T(n/2) + n log a
Usando o teorema mestre, a = 4, b = 2 e f(n) = n teremos n b = n² . Teremos que f (n) = O(n 2−e) se e = 1 . Isso significa que T (n) = Θ(n²) . ii) T(n) = 4T(n/2) + n² log a
Aqui teremos a = 4, b = 2 e f(n) = n² teremos n b = n² . Teremos