2
$\begingroup$

$T(n) =$ if $n=1$, then time execution is $1$, if $n \geq 2$ then $2T(n-1)+n$

The options are:

  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)$

Thanks.

  • 0
    Right JeffE, multiple choices are allowed.2012-05-12

1 Answers 1

3

Ignoring the choices you have for the time being, here is how we could start out.

Define $S(n)=2^{-n}T(n)$, then, after multiplying by $2^{-n}$, the recurrence becomes $ S(n)=S(n-1)+\frac{n}{2^n}\tag{1} $ Equation $(1)$ tells us that $S(n)$ is the finite sum $ c+\sum_{k=1}^n\frac{k}{2^k}\tag{2} $ where $c$ is a constant chosen so that $S(1)=\frac12$.