Lista de exercícios - 1

---

Gabriel Ken Kazama Geronazzo (10418247)

Simule a execução do mergesort para o vetor abaixo. Lembre-se de chamar a primeira linha recursiva de m1, a segunda de m2 e a intercalação de m (ou seja, simule conforme visto em aula).

$$v:\begin{array}{cccccccc}2& 8& 1& 9& 7& 5& 3& 0\end{array}$$ $$m1:\begin{array}{cccc}2& 8& 1& 9\end{array}$$ $$m1:\begin{array}{cc}2& 8\end{array}$$ $$m1:\begin{array}{c}2\end{array}m2:\begin{array}{c}8\end{array}$$ $$m:\begin{array}{cc}2& 8\end{array}$$ $$m2:\begin{array}{cc}1& 9\end{array}$$ $$m1:\begin{array}{c}1\end{array}m2:\begin{array}{c}9\end{array}$$ $$m:\begin{array}{cc}1& 9\end{array}$$ $$m:\begin{array}{cccc}1& 2& 8& 9\end{array}$$ $$m2:\begin{array}{cccc}7& 5& 3& 0\end{array}$$ $$m1:\begin{array}{cc}7& 5\end{array}$$ $$m1:\begin{array}{c}7\end{array}m2:\begin{array}{c}5\end{array}$$ $$m:\begin{array}{cc}5& 7\end{array}$$ $$m2:\begin{array}{cc}3& 0\end{array}$$ $$m1:\begin{array}{c}3\end{array}m2:\begin{array}{c}0\end{array}$$ $$m:\begin{array}{cc}0& 3\end{array}$$ $$m:\begin{array}{cccc}0& 3& 5& 7\end{array}$$ $$m:\begin{array}{cccccccc}0& 1& 2& 3& 5& 7& 8& 9\end{array}$$

Resolva sem usar o Teorema Mestre as recorrências abaixo.

1. $T(n)=3T(n-1)+n$

$$T(n)=3T(n-1)+n$$

Sabendo que $T(n-1)=3T(n-2)+n-1$, temos:

$$T(n)=3(3T(n-2)+n-1)+n$$ $$T(n)=3^{2}T(n-2)+3(n-1)+n$$

Sabendo que $T(n-2)=3T(n-3)+n-2$, temos:

$$T(n)=3^2(3T(n-3)+n-2)+3(n-1)+n$$ $$T(n)=3^{3}T(n-3)+3^2(n-2)+3^1(n-1)+3^0(n-0)$$

Generalizando

$$T(n)=3^i\cdot T(n-i)+\sum _{k=0}^{i-1}{3}^k(n-k)$$

E vai para quando $n-i=1\Rightarrow i=n-1$

$$T(n)=3^{n-1}\cdot \text{cancelto}1T(1)+\sum _{k=0}^{n-2}{3}^k(n-k)$$ $$T(n)=3^0(n-0)+3^1(n-1)+3^2(n-2)+\cdots +3^{n-2}(2)+3^{n-1}(1)$$ $$T(n)=\frac{n(n+3^{n-1})}{2}=\frac{n(n+\frac{3^n}{3})}{2}=\frac{n^2+\frac{3^n}{3}n}{2}$$ $$T(n)=\frac{n^2}{2}+\frac{3^{n}n}{6}=\frac{3n^2+3^{n}n}{6}$$ $$T(n)=\theta (2^n)$$

2. $T(n)=9T(\frac{n}{3})+n$

$$T(n)=9T(\frac{n}{3})+n$$

Sabendo que $T(\frac{n}{3})=9T(\frac{n}{3^2})+\frac{n}{3}$, temos:

$$T(n)=9(9T(\frac{n}{3^2})+\frac{n}{3})+n$$ $$T(n)=9^{2}T(\frac{n}{3^2})+3n+n$$

Sabendo que $T(\frac{n}{3^2})=9T(\frac{n}{3^3})+\frac{n}{3^2}$, temos:

$$T(n)=9^2(9T(\frac{n}{3^3})+\frac{n}{3^2})+3n+n$$ $$T(n)=9^{3}T(\frac{n}{3^3})+9n+3n+n$$

Generalizando:

$$T(n)=9^{i}T(\frac{n}{3^i})+\sum _{k=0}^{i-1}{3}^{k}n$$

E vai parar quando $\frac{n}{3^i}=1\Rightarrow n=3^i\Rightarrow i={\log }_{3}n$ .

$$T(n)=9^{lo{g}_{3}n}\text{cancelto}1T(1)+\sum _{k=0}^{lo{g}_{3}n-1}{3}^{k}n$$ $$T(n)=(3^2{)}^{lo{g}_{3}n}+\sum _{k=0}^{lo{g}_{3}n-1}{3}^{k}n$$ $$T(n)=3^{2\cdot lo{g}_{3}n}+\sum _{k=0}^{lo{g}_{3}n-1}{3}^{k}n$$ $$T(n)=3^{lo{g}_3{n}^2}+\sum _{k=0}^{lo{g}_{3}n-1}{3}^{k}n$$ $$T(n)=n^2+\sum _{k=0}^{lo{g}_{3}n-1}{3}^{k}n$$ $$T(n)=n^2+\sum _{k=0}^{\frac{lo{g}_n}{lo{g}_3}-1}{3}^{k}n$$ $$T(n)=n^2+\frac{1}{2}(n-1)n$$ $$T(n)=n^2+\frac{n^2}{2}-\frac{n}{2}$$ $$T(n)=\frac{2n^2}{2}+\frac{n^2}{2}-\frac{n}{2}$$ $$T(n)=\frac{3n^2-1}{2}$$ $$\therefore T(n)=\theta (n^2)$$

Referências

---

• Lista_1___Proj_Alg1__1s24_