1
$\begingroup$

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

$\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
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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