I am wondering if there is a way to solve a recurrence time function with the master theorem if no $b$ exists. Like in this case. $$ T(n) = 2\times T(n-1)+4$$
$\begingroup$
$\endgroup$
-
$\begingroup$ No b exists and b=0 are different things. $\endgroup$ – zkutch Nov 29 '20 at 15:11
-
$\begingroup$ The master theorem is useful for many recurrences, but it isn't the correct tool for all of them. $\endgroup$ – Yuval Filmus Nov 29 '20 at 15:44
$\begingroup$
$\endgroup$
By expansion you can see it is $T(n) = \Theta(2^n)$ (suppose $T(1) = 1$):
$$ T(n) = 2T(n-1) +4 = 2(2T(n-2)+4) + 4 = 2^2T(n-2) + 2\times 4 + 4 = \ldots = $$
$$ 2^{n-1}T(1) + 2^{n-2}4 + \cdots + 4 = 4\left(\sum_{i=1}^{n-1}2^i\right) = 4(2^n - 1) $$
$\begingroup$
$\endgroup$
Let $S(n) = T(n)/2^n$. Then $$ S(n) = S(n-1) + \frac{4}{2^n}. $$ Since the series $\sum_{n=1}^\infty \frac{4}{2^n}$ converges, we see that $S(n) = \Theta(1)$, and so $T(n) = \Theta(2^n)$.
answered Nov 29 '20 at 15:45
