I am reading a free algorithms textbook http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf and on page 13 i am stuck on an example they give.

"At this time, the fastest computer in the world is the NEC Earth Simulator, which clocks 40 trillion steps per second. Even on this machine, fib1(200) would take at least 2^92 seconds"

im stuck on how the got 2^92

here is the relevant information:

pseudo code:

enter image description here

given that:

T(n) ≤ 2 for n ≤ 1.

T(n) = T(n − 1) + T(n − 2) + 3 for n > 1

So i think we start by plugging n = 200

T(200) = T(199) + T(198) + 3

and then i do not know where to go from here

Any help on this is much appreciated

  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Sep 10 '17 at 16:46
  • 1
    $\begingroup$ Have you looked up properties of the Fibonacci numbers? There are closed formulas for the value of fib1(n). Figure out how the running time of fib1 relates to the Fibonacci numbers! What is the recurrence for the running time? $\endgroup$ – Raphael Sep 10 '17 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.