3
$\begingroup$

I am trying to prove the recurrence $2T(n-1) + 1$ has the bound $\theta(2^{n})$. $T(1) = \theta (1)$

My attempted solution:

\begin{align*} T(n) &= 2T(n-1) + 1 \\ &= 2 \{ 2T(n-2) + 1 \} + 1 \\ &= 2 \{ 2 \{ 2T( n - 3 ) + 1 \} + 1 \} + 1 \\ & \ldots \\ &= 2^{i}T(n-i)+\sum_{i=0}^{k} 2^{i} + 1. \end{align*}

I then proceed to substitute $n-1$ for $i$ which gives me

\begin{align*} & 2^{n-1}T(n-(n-1)) + \sum_{i=0}^{n-1} 2^{i} + 1 \\ &= 2^{n-1}T(n-n+1) + \sum_{i=0}^{n-1} 2^{i} + \sum_{i=0}^{n-1} 1 \\ &= 2^{n-1}T(1) + 2^{n-1+1} + n - 1 \\ &= 2^{n-1}\theta(1) + 2^{n} + n - 1\\ \end{align*}

At this point I can see that $2^{n}$ is the dominating factor, however in the solution hints of my book it states that I should use $i = n$. However when I do that I get $T(0)$.

I suspect there is something wrong with my substitution/unraveling step, however I can't seem to figure it out. Any help would be appreciated

  • 0
    Your fourth step should be $T(n) = 2^k T(n-k) + \sum_{i=1}^k 2^{i-1}$2011-03-03

2 Answers 2

3

Your fourth step should be $T(n) = 2^k T(n-k) + \displaystyle \sum_{i=1}^k 2^{i-1}$ and there are a few errors in your manipulation.

A simpler way to go about would be to let $T(n) = f(n) - 1$. Plugging this in the recurrence, we get $f(n)-1 = 2(f(n-1)-1) + 1$ i.e. $f(n) = 2f(n-1)$ Solving this recurrence is child's play and we get $f(n) = f(1) 2^{n-1}$ and hence $T(n) = f(1) 2^{n-1} - 1 = T(1) 2^{n-1} + 2^{n-1} - 1 $ since $f(1) = T(1) + 1$

1

Maybe here?

$\begin{align*} T(n) &= 2T(n-1) + 1 \\ &= 2 \{ 2T(n-2) + 1 \} + 1 \\ &= 2 \{ 2 \{ 2T( n - 3 ) + 1 \} + 1 \} + 1 \\ & \ldots \\ &= 2^{i}T(n-i)+\sum_{k=1}^{i-1} 2^{k} + 1. \end{align*}$

Also, $ \begin{align*} & 2^{n-1}T(n-(n-1)) + \sum_{i=1}^{n-2} 2^{i} + 1 \\ &= 2^{n-1}T(n-n+1) + \sum_{i=1}^{n-2} 2^{i} + 1 \\ &= 2^{n-1}T(1) + 2^{n-1} -1 \\ &= 2^{n-1}\theta(1) + 2^{n-1} - 1\\ \end{align*}$