1
$\begingroup$

Can I solve T(n) = 2T(n − 1) + 1 using the master theorem method? I don't think it cannot be solved with the master theorem because b=1. Please let me know, if my guess is wrong.

$\endgroup$
2
2
$\begingroup$

Here are several ways of solving this recurrence. Throughout, I will assume that $T(0) = 0$.

Method 1: Guessing

Here are some values of $T(n)$: $$ \begin{array}{c|cccccc} n & 0 & 1 & 2 & 3 & 4 & 5 \\\hline T(n) & 0 & 1 & 3 & 7 & 15 & 31 \end{array} $$ If you're familiar with powers of 2, you will recognize that $T(n) = 2^n-1$. If not, you can look it up on the Online Encyclopedia of Integer Sequences, where you will find it as A000225, under the name Mersenne numbers.

Method 2: Homogenization

We look for a related recurrence without the "$+1$". The first think one could try is replacing $T(n)$ with $S(n) = T(n) + C$, which satisfies the recurrence $$ S(n) = T(n) + C = 2T(n-1) + C + 1 = 2S(n-1) - C + 1. $$ We see that if $C = 1$ then $S(n) = 2S(n-1)$, and so $S(n) = 2^n S(0) = 2^n$. We conclude that $T(n) = 2^n - 1$.

Method 3: Reduction

The recurrence makes it clear that the first order asymptotics of $T(n)$ should be related to $2^n$, and so suggests considering $R(n) = T(n)/2^n$, which satisfies the recurrence $$ R(n) = \frac{T(n)}{2^n} = \frac{T(n-1)}{2^{n-1}} + \frac{1}{2^n} = R(n-1) + \frac{1}{2^n}. $$ This shows that $$ R(n) = R(0) + \sum_{m=1}^n \frac{1}{2^m} = 1 - \frac{1}{2^n}, $$ and so $T(n) = 2^n - 1$.

If we are only interested in the asymptotics, we could notice that since the series $\sum_{n=1}^\infty \frac{1}{2^n}$ converges, we clearly have $R(n) = \Theta(1)$, and so $T(n) = \Theta(2^n)$.

Method 4: Generating series

We could also solve the recurrence automatically using generating series. Let $$ P(x) = \sum_{n=0}^\infty T(n) x^n. $$ Then $$ P(x) = T(0) + \sum_{n=1}^\infty T(n) x^n = 2\sum_{n=1}^\infty T(n-1) x^n + \sum_{n=1}^\infty x^n = 2xP(x) + \frac{x}{1-x}. $$ We conclude that $$ P(x) = \frac{x}{(1-x)(1-2x)} = \frac{1}{1-2x} - \frac{1}{1-x} = \sum_{n=0}^\infty (2^n - 1) x^n. $$ Therefore $T(n) = 2^n - 1$.

Method 5: Combinatorial interpretation

This method is more creative. We find some combinatorial object which we already know how to count, and we show that it satisfies the same recurrence. In this case, we could choose all non-empty subsets of $\{1,\ldots,n\}$. Each such subset is either obtained from a non-empty subset of $\{1,\ldots,n-1\}$ by either adding or not adding $n$, and additionally the subset $\{n\}$, which does not arise in this way. The base cases also match, and so $T(n) = 2^n - 1$.

$\endgroup$
1
$\begingroup$

You can only solve equations using the Master Theorem if they are of form $T(n) = aT(n/b) + f(n)$, where $a \ge 1$ and $b > 1$.

Here you can't express your recurrence in above form. And your guess of taking $b = 1$ is completely wrong. The reason for not using the Master Theorem is that you can't express your recurrence in form $T(n) = aT(n/b) + f(n)$ where $a \ge 1$ and $b > 1$. You would able to use the Master Theorem if the equation were $T(n) = 2T(n/2) + 1$, in which case $a = 2$ and $b = 2$.

In order to solve your recurrence equation $T(n) = 2T(n-1) + 1$, you will have to use a recursion tree, and then verify the solution using induction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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