Question

long fib(int n)
{
long result;
  
if (n==0)
result = 0;
else if (n==1 || n==2)
result = 1;
else
result = fib(n-1) + fib(n-2);
  
return result;
}

[C language]

Question : Why is this code is so slow? Explain

ex2)

Make the program from exercise 1 faster by trading space for time. Create an array of int that can be used as

a cache. Each index in the array should correspond to a value that you can compute once, then quickly return.

Pick two different sizes for your cache (one small, one large, you’re going to need to figure out what reasonable values for small and large are on your own). Run the same experiment that you did in exercise 1 for both the small cache and the large cache and plot the results in the same way.

Report:

Upload the updated chart. Make a note in any empty cell why the program runs faster (“Because we’re trading space for time” is not a good enough answer…) and explain how the size of the cache affects the runtime.

Answer 1

please upvote.