Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been working through my homework paper, and I've come across this question. Now I'm confident in what I have done for the most part, but I am stuck at the end.

I have this recurrence relation, that I am supposed to solve using backward substitution.

$$ T(n) = 2T(n/2) + n + 11 $$

Where n is some power of 2, for all n>1 and T(1) = 0.

I started out by some backward substitution and eventually arrived at this:

$$ 2^3T(n/2^3) + 2^2(n) + 2^2(11) + 2(n) + 2(11) + n + 11 $$

And I reasoned that the general case was:

$$ 2^kT(n/2^k) + 2^{k-1}(n) + 2^{k-1}(11) + 2^{k-2}(n) + 2^{k-2}(11)...2^0(n) + 2^0(11) $$

n is a power of two, meaning that I can resolve this further:

$$ T(n) = 2^{k-1}(n) + 2^{k-1}(11) + 2^{k-2}(n) + 2^{k-2}(11)...2^0(n) + 2^0(11) $$

Now I know I am supposed to summate this in some way, but I really don't know how! Can you guys point me in the right direction please?

Second attempt

I started from the beginning again, and this is how I went. I can see my answer coming closer to yours now, but I'm just struggling with one bit.

$$ T(n) = 2T(n/2) + n + 11 $$

$$ T(n) = 2^2T(n/4) + n/2 + n + 22 + 11 $$

$$ T(n) = 2^3T(n/8) + n/4 + n/2 + n + 44 + 22 + 11 $$

Factorized the 11..

$$ T(n) = 2^3T(n/8) + n/4 + n/2 + n + 11(4 + 2 + 1) $$

I'm struggling to get from this point to your answer. Sorry to be such a pain!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Well $$\sum_{j=0}^{k-1} 2^j = 2^k-1$$ since it's just a geometric sum of ratio 2.

But let's check your substitution: $$T(2^k) = 2 T(2^{k-1}) + 2^k + 11 = 2 \left(2 T(2^{k-2}) + 2^{k-1} + 11\right) + 2^k + 11$$ or $$2^2T(2^{k-2}) + 2\times 2^k + (2 + 1)\times 11$$ Adding another term gives $$2^2\left(2T(2^{k-3}) + 2^{k-2} + 11\right) + 2\times 2^k + (2 + 1)\times 11$$ or $$2^3T(2^{k-3}) + 3\times 2^k + (4 + 2 + 1)\times 11$$

Edit: Note that you accidentally substituted in $T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) + \boxed{n} + 11$. The boxed term should be $\frac{n}{2}$. Then you accidentally left out the $\boxed{2} \times 2^{k-1}$ and the $\boxed{2\times 2}\times2^{k-2}$ etc.

In general, we get $$2^k T(1) + k 2^k + (1 + 2 + \cdots + 2^{k-1})\times 11 = k 2^k+11(2^k-1)$$ or $$T(2^k) = (k+11)2^k-11$$

share|improve this answer
    
So is my substitution incorrect? I'm sorry, I'm really not following your explanation. –  notverygoodatmaths Apr 15 '13 at 20:15
    
Yes - you forgot that when you substitute in for $T(n/2)$, you get $2T(n/4) + \boxed{n/2} + 11$ –  Sharkos Apr 15 '13 at 23:10
    
Oh jesus of course! I'll have another look and give it another go. :) –  notverygoodatmaths Apr 15 '13 at 23:11
    
No worries! Sorry, I'll point it out in the answer for clarity. (I wanted to go through the whole question to make sure the technique worked easily, and there weren't any other mistakes.) –  Sharkos Apr 15 '13 at 23:13
    
Hi, please look at my edit. I gave it another go but I hit a bit of a stumbling block, Sorry! –  notverygoodatmaths Apr 15 '13 at 23:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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