Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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


share|improve this question
What have you tried? –  lhf May 11 '12 at 0:12
The first choice seems satisfying what the properties you listed exactly. –  Shuhao Cao May 11 '12 at 0:12
I've removed the "complex-analysis" tag since this isn't related to complex analysis. –  Antonio Vargas May 11 '12 at 0:37
Define $T(n) = f(n) -n -2$. And see if you can get $f(n)$ easily. –  user17762 May 11 '12 at 3:42
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. –  joriki May 11 '12 at 6:57

1 Answer 1

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.