1
$\begingroup$

We started learning recurrences and I am having trouble with some of the problems. Our professor is having us substitute in $n=2^m$ and $S(m)=T(2^m)$ then writing down equations and summing them all up. I understand the substitution part, but not how to simplify the end result.

One of the problems I am stuck on is $T(n)=2T(n/2)+n^3$ where $T(2)=c$, When I sub in $n=2^m$ and $S(m)=T(2^m)$ I get:

$S(m)=2S(m-1)+(2^m)^3$

$S(m-1)=2S(m-2)+(2^{m-1})^3$

...

$S(3)=2S(2)+(2^{3})^3$

$S(2)=2S(1)+(2^{2})^3$

$S(1)=c$

Now because there is a coefficient on the right side we have to multiply each equation by a power of 2 so we can sum them.

$S(m)=2S(m-1)+(2^m)^3$

$2*S(m-1)=2^2S(m-2)+2*(2^{m-1})^3$

...

$2^{m-3}*S(3)=2^{m-2}S(2)+2^{m-3}(2^{3})^3$

$2^{m-2}*S(2)=2^{m-1}S(1)+2^{m-2}(2^{2})^3$

$2^{m-1}S(1)=c*2^{m-1}$

So sum these and we get:

$S(m)=(2^m)^3+2*(2^{m-1})^3+2^2*(2^{m-2})^3+...+2^{m-3}(2^{3})^3+2^{m-2}(2^{2})^3+c*2^{m-1}$

And this is where I get stuck, how can I simplify this? I tried dividing by $(2^m)^3$ but that came out to a awful mess. The other two I'm having trouble with are $T(n)=16T(n/4)+n^2$ and $T(n)=7T(n/2)+n^2$ Any help would be appreciated.

$\endgroup$
1
  • $\begingroup$ You may want to have a look at our reference question on solving recurrences. $\endgroup$
    – Raphael
    Commented Sep 17, 2013 at 7:58

1 Answer 1

2
$\begingroup$

Once you have $S(m) = 2 S(m-1) + 2^{3m}$, you can divide by $2^m$ and obtain : $$\frac{S(m)}{2^m} = \frac{S(m-1)}{2^{m-1}} + 2^{2m}$$ Thus, setting $P(m) = \frac{S(m)}{2^m}$, you should be able to find $P(m)$, then $S(m)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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