Sort1

Uma vez sabendo a complexidade de tempo do procedimento MERGE, sigamos para o cálculo da complexidade de tempo do algoritmo Sort1 como um todo.

$$T\left( n\right) =2T(n/2)+O(n)$$

Aplicando o Master Theorem[1, p62], tendo que , e , chegamos ao resultado que

$$f\left( n\right) =\Theta \left( n^{\log _{b}a}\right) \Right... ...eft( n^{\log _{2}2}\log n\right) =\Theta \left( n\log n\right)$$

Já temos uma idéia do que procurar. Desenvolvamos a equação recursiva por substituições:

$$\begin{eqnarray*} T\left( n\right) & = & 2T(\frac{n}{2})+O(n)\\ & = & 4T\left(... ...t) & = & 2^{i}T\left( \frac{n}{2^{i}}\right) +iO\left( n\right) \end{eqnarray*}$$

Fazendo

$$\begin{eqnarray*} T\left( n\right) & = & n+O(n)\lg n\\ & = & o(n\lg n) \end{eqnarray*}$$