lista2.md 1.5 KB
1.Resolva as recorrências abaixo:
Em todos esses exercíccios vamos escrever a recorrência, assumir um monte de coisa, chegar em uma fórmula e por último provar que estamos certos. Tamb;em vamos supor que para todas recorrências $T(1) = 1$
A) $T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n^2)$
$$T(n) = 2T(\lfloor n/2 \rfloor) + cn^2 \leq 2T( n/2 ) + cn^2$$ $$T(n) \leq 2(2T( n/4 ) + cn^2/2^2) + cn^2 = 4T( n/4 ) + cn^2 + cn^2$$ $$T(n) \leq 2^iT( n/2^i ) + icn^2$$
Suponha que n = 2^i (potência de 2):
$$T(n) \leq 2^iT( 1 ) + icn^2$$ $$T(n) \leq 2^i + icn^2 = n + c lg \space (n) n^2$$
Portanto é $O(n^2)$. Note que não provamos que é $\Theta$ de alguma coisa, somente $O$, isso se deve ao fato de estarmos escolhendo um limitante superior qunado removemos o chão do número. Poderíamos achar $\Omega$, se quissésemos.
Vamos provar isso por indução, sabendo que nossa hpótese é $T(n) \leq bn^2$. Note que para a base isso é verdade, pois $T(N) = 1 \leq b \cdot 1^2$.
$$T(n) = 2T(n/2) + cn^2$$
Pela hipótese de indução:
$$T(n) = 2T(n/2) + cn^2 \leq 2 b(n/2)^2 + cn^2 = b(n^2/2) + cn^2 = bn^2 + n^2 (- b/2 + x) $$
Se $- b/2 + x \leq 0$ ($c$ e $b$ devem ser constantes maiores que 0, suponha $b = 4$ e $c = 2$), vale
$$T(n) \leq bn^2$$
Que é o que queríamos provar. Note que também poderíamos utilizar como hipótese de indução $T(n) \leq n + c lg \space (n) n^2$. A prova daria no final na mesma.
B) $T(n) = 8T(\lfloor n/2 \rfloor) + \Theta(n^2)$