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:
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