Análise assintótica para o algoritmo de merge sort

---

$$\{\begin{array}{l}T(n)=2T\frac{n}{2}+n\\ T(1)=1\end{array}$$

Para encontrar a fórmula fechada para esta fórmula aberta devemos calcular esta recorrência.

Calcule $T(n)=2T\frac{n}{2}+2$, com $T(1)=1$ mas:

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

mas:

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

Generalizando, temos:

$$T(n)=2^i\cdot T(\frac{n}{2})+\sum _i^{k=1}n$$

e vai parar quando $\frac{n}{2^i}=1$

$$2^i=n\to i={\log }_{2}n\therefore T(n)=2^{{\log }_{2}n}\cdot T(1)+\sum _{k=1}^{{\log }_{2}n}$$ $$T(n)=n^{{\log }_{2}n}\cdot 1+n\log n=n+n\log n\therefore T(n)=\theta (n\log n)$$

Referências

---