Análise assintótica - Exemplo 4

---

A forma aberta de um algoritmo é $T(n)=2T(n-1)+n$, então a forma generalizada por ser encontrada da seguinte forma:

$$T(n)=2T(n-1)+1$$ $$\text{Sabendo que }T(n-1)=2T(n-2)+1$$ $$T(n)=2(2T(n-2)+1)+1$$ $$T(n)=2^{2}T(n-2)+2+1$$ $$\text{Sabendo que }T(n-2)=2T(n-3)+1$$ $$T(n)=2^2(2T(n-3)+1)+2+1$$ $$T(n)=2^{3}T(n-3)+2^2+2^1+2^0$$

Generalizando $T(n)=2^{i}T(n-i)+{\sum }_{k=0}^{i-1}{2}^k$ e vai parar quando $n=i-1$

$$\therefore T(n)=2^{n-1}\cdot T(1)+\sum _{k=0}^{i-1}{2}^k=2^{k-1}+(\frac{2^{n-1}-1}{2-1})$$ $$\therefore T(n)=2^{n-1}\Rightarrow T(n)=\theta (2^n)$$

Referências

---