2

Suppose a Fibonacci algorithm:

enter image description here

We are asked to prove the upper/lower bound of this algorithm.

How do I proceed?

Update

So I'll explain what I have done myself and show where I'm stuck.

I don't know why but I decided to use recurrence relation here to see where I can get my final result. But the reason why I doubt my working out is that Upper/lower bound is the identification of the "limitless" of an algorithm in terms of resources.

So, the parallel algorithm has:

Work(n) = W(n - 1) + W(n - 2) + Θ(1)

At this point, I decided to use recurrence relation - have no idea -

Work(n) = [W(n - 1) + W(n - 2) + Θ(1)] + W(n - 2) + Θ(1)
        = W(n - 2) + W(n - 2) + 2Θ(1)
        = 2W(n - 2) + 2
        = Stuck here

Honestly, I don't know even if that makes sense.

A formal solution was given: enter image description here

But I didn't quite understand the steps that were taken above

S. Nas
  • 331
  • 1
  • 4
  • 14
  • My reason for NOT voting to close: Lacks research, but a good question. – displayName Jan 07 '18 at 18:03
  • Sorry, am I missing something important to my question? I can explain in more details. @displayName – S. Nas Jan 07 '18 at 18:12
  • If you have invested effort in solving the question before asking on SO, please add in here all that you tried. – displayName Jan 07 '18 at 18:15
  • Ah, sure thing will add the solution. Although it's not meaningful and completely wrong as I have no clue how to even start. But will update above. @displayName – S. Nas Jan 07 '18 at 18:32
  • Thank you for your answer, I'll read now. Please also have a look at my updated question for showing my work (although pointless) @displayName – S. Nas Jan 07 '18 at 18:48
  • 1
    Looking at the sample solution at the end, I think that my answer is wrong. I got confused with the line "in the context [of] processors" in your question. I'll wait to delete until you have read it because if I delete it before, you won't be able to see it anymore due to low rep. – displayName Jan 07 '18 at 19:09
  • Apologies! Entirely my fault. I have copied the answer regardless because I need to understand how to think for problems like these. You can go ahead and delete the answer. @displayName – S. Nas Jan 07 '18 at 19:17
  • What exactly are you required to prove the lower/upper bound of (for multi-processing, you can go for work done or time taken, and that can be per processor or in total, and those can all be different)? Is there any specification on the amount of processors available? Is it arbitrarily many / infinite? – Bernhard Barker Jan 07 '18 at 19:18
  • The requirement is for multiprocessing (Work(n)). It is arbitrary, and assume we have infinite amount of processors @Dukeling – S. Nas Jan 07 '18 at 19:20
  • W(n-1) + Θ(1) >= W(n-2), thus W(n-1) + W(n-2) + Θ(1) >= 2W(n-2). The next step follows from the fact that W(n-2) >= 2W(n-4), thus W(n) >= 4W(n-4), W(n) >= 8W(n-6), etc. until we get to W(0). – Bernhard Barker Jan 07 '18 at 20:23
  • @greybeard Apologies, there was a mistake there. Please ignore that. Assume we are given an infinite number of processors, and find the upper/lower bound of the algorithm – S. Nas Jan 08 '18 at 07:13

1 Answers1

0

I would say that the processors are of almost no concern since the recurrence is a tree and this tree has an exponential number of nodes. These nodes represent the merge that has to be done in each step. So even if the number of processors is unlimited it does not help solving this recurrence as they can only compute something independently in the last row, i.e., W(1) and W(0).

I just saw in the comments that the sample solution was supplied and partially explained: Here some further "insight": The idea is to expand the recurrence and look for a way to collect the factors. Here they collect the 2 in a way that they apply an inequality: W(n-1)+W(n-2) >= 2 W(n-2). So now you have W(n)>= 2 W(n-2). How often do we subtract the 2 until we have W(0) on the right side? n/2 times. Then you end up with the Omega(2^(n/2)) lower bound. You can use the more or less same approach to show an upper bound.

Just as a small side note, these bounds are not tight: Related Post

gue
  • 1,868
  • 1
  • 16
  • 21