Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

$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|cite|improve this question

marked as duplicate by Famous Blue Raincoat, Brian Fitzpatrick, ncmathsadist, Lord_Farin, quid Feb 21 '15 at 21:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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
You're right joriki. Thanks – Albert May 11 '12 at 18:16

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|cite|improve this answer

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