Forma o comportamiento asintótico de $T(n) =2T(n-1)+n$

Question

$T(n) =$ si $n=1$ , entonces el tiempo de ejecución es $1$ , si $n \geq 2$ entonces $2T(n-1)+n$

Las opciones son:

1. $T(n) = 2^{n+1} - n - 2$
2. $T(n) = O(n2^n)$
3. $T(n) = \Omega(n)$
4. $T(n) = \theta(2^n)$

Gracias.

Answer 1

Ignorando las opciones que tienes por el momento, así es como podríamos empezar.

Definir $S(n)=2^{-n}T(n)$ y después de multiplicar por $2^{-n}$ la recurrencia se convierte en $$ S(n)=S(n-1)+\frac{n}{2^n}\tag{1} $$ Ecuación $(1)$ nos dice que $S(n)$ es la suma finita $$ c+\sum_{k=1}^n\frac{k}{2^k}\tag{2} $$ donde $c$ es una constante elegida para que $S(1)=\frac12$ .