0

I have this recurrence:

W(n)= 2W(floor(n/2)) + 3
W(2)=2

My try is as follow:

the tree is like this:

W(n) = 2W(floor(n/2)) + 3
W(n/2) = 2W(floor(n/4)) + 3
W(n/4) = 2W(floor(n/8)) + 3 
...
  • the hight of the tree : I assume its lgn because the tree has 2 branches at every expanding process, not sure though :S
  • the cost of the last level : 2^lgn * W(2) = 2n
  • the cost of all levels until level h-1 : 3 * sigma from 0 to lgn-1 of (2^i), which is a geometric series = 3 (n-1)

So, T(n) = 5n - 3 which belong to Theta(n)

my question is: Is that right?

1
  • height is lgn because at each level the size of input is being cut into half and this is by definition log base 2. Another way of looking at it is that log is inverse of power
    – MARK
    Nov 29, 2011 at 20:31

2 Answers 2

1

I don't think it's exactly 5n-3 except n is 2t, but your theta is right if you look at Master Theorem, there is no need to calculate it (but its good for startup):

assume you have:

T(n) = aT(n/b) + f(n), where a>=1, b>1 then:

  1. if f(n) = nlogba-eps for any eps > 0 then T(n) = nlogba like your case, in which a=b=2, f(n) = O(1).
  2. f(n) = Theta(nlogba * logkn) then T(n)=Theta(nlogba * logk+1n).
  3. Otherwise is Theta(f(n)). (see detail of constraint in this case in CLRS or wiki, ...)

for detail see wiki.

2
  • I can't use the master theorem in this question, so I'm trying to get it right with the recursion tree.. thnx a lot for ur answer mr.Amiri
    – Sosy
    Nov 29, 2011 at 20:52
  • @Sosy I suggest to read master theorem proof it will helps you a lot, later. Nov 29, 2011 at 21:04
1

Well, if you calculate W(4), you find W(4) = 2*W(2) + 3 = 2*2 + 3 = 7, but 5*4 - 3 = 17, so your result for T(n) is not correct. It is close, though, there's just a minor slip in your reasoning (or possibly in a certain other place).

Edit: To be specific, your calculation would work if W(1) was given, but it's W(2) in the question. Either the latter is a typo or you're off by one with the height. (and of course, what Saeed Amiri said.)

1
  • hmm, I'm pretty sure that my mistake is in finding the cost per level at the last level, what I did is: (2^lg n)(W(2)) because I think the size of the subproblems will be reduced to 2 at the last level. is that right?
    – Sosy
    Nov 29, 2011 at 20:57

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.