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
    The first choice seems satisfying what the properties you listed exactly.2012-05-11
  • 0
    I've removed the "complex-analysis" tag since this isn't related to complex analysis.2012-05-11
  • 2
    Define $T(n) = f(n) -n -2$. And see if you can get $f(n)$ easily.2012-05-11
  • 0
    The title is wrong; you're not looking for the complexity of this function; you're looking for a closed form for it (option 1) or its asymptotic behaviour (options 2 to 4). This is probably related to the time complexity of a an algorithm, but complexity is a property of the algorithm, not of the function specifying its execution time.2012-05-11
  • 0
    You're right joriki. Thanks2012-05-11
  • 0
    Are you allowed to pick more than one option?2012-05-11
  • 0
    Right JeffE, multiple choices are allowed.2012-05-12

1 Answers 1