Question

MATLAB

1. The Fibonacci sequence is defined by the recurrence relation Fn = Fn-1+Fn-2 where Fo = 0 and F1 = 1. Hence F2 = 1, F3 = 2, F4 = 3, etc. In this problem you will use three different methods to compute the n-th element of the sequence. Then, you will compare the time complexity of these methods. (a) Write a recursive function called fibRec with the following declaration line begin code function nElem = fibrec (n) end code where the input argument n is the element of the Fibonacci sequence that should be computed and returned to the output argument, nElem. This function should use recursion to compute the desired value. (b) Write a function called fibLoop with the following declaration line begin code function nElem = fibLoop(n) end code 1 1 of 2 Available: July 14 Summer 2016 Due: August 7 where the input argument n is the element of the Fibonacci sequence that should be computed and returned to the output argument, nElem. This function should use a for loop to compute the desired value. (c) The n-th element of the Fibonacci sequence can also be determined by the closed form equation: pelle - (1-r)" Fn = where s= 1+5 2 V5 Write a function called fibEqn with the following declaration line begin code function nElem = fibEqn(n) end code 1 where the input argument n is the element of the Fibonacci sequence that should be computed and returned to the output argument, nElem. This function should use the closed form equation given above to compute the desired value. (d) Next, compare the asymptotic time complexity of the three functions you created. To this end, measure the time it takes each functions to execute for n = 1:25. For each value of n run each function three times and compute the average amount of time it takes the functions to run. Finally, plot the average run-time of each function versus the value of n. Label your figure and the axes suitably and add a legend to your figure. Make sure this figure appears in the pdf file that you upload to Canvas.

Answer 1

MATLAB code:

% measuring the time taken by each of function for n = 1 to 25

timerec = zeros(1 , 25);

timeloop = zeros(1 , 25);

timeEqn = zeros(1 , 25);

for n = 1 : 25

tic; fibrec(n);

timerec(n) = toc;

tic; fibloop(n);

timeloop(n) = toc;

tic; fibEqn(n);

timeEqn(n) = toc;

end

% Plotting the graph

plot([1:25] , timerec , [1:25] , timeloop , [1:25] , timeEqn);

xlabel('n')

ylabel('Average time')

legend('timerec' , 'timeloop' , 'timeEqn');

% Writing recursive code to calculate fibonacci number

function nelem = fibrec(n)

if(n == 0)

nelem = 0;

elseif(n == 1)

nelem = 1;

else

nelem = fibrec(n - 1) + fibrec(n - 2);

end

end

% Writing iterative code

function nelem = fibloop(n)

n_second_prev = 0;

n_prev = 1;

for i = 2 : n

nelem = n_prev + n_second_prev;

n_second_prev = n_prev;

n_prev = nelem;

end

end

% Writing closed form function

function nelem = fibEqn(N)

r = (1 + sqrt(5)) / 2;

nelem = round(((r^N) - ((1 - r) ^ N)) / sqrt(5));

end

1 2 3 4 5 6 % measuring the time taken by each of function for n = 1 to 25 timerec = zeros(1, 25); time loop = zeros(1, 25); timeEqn = zeros(1 , 25); for n = 1 : 25 tic; fibrec(n); timerec(n) = toc; - 7 tic; fibloop(n); time loop(n) = toc; 1 tic; fibean(n); timeEqn(n) = toc; end 8 9 10 11 12 13 14 15 16 17 18 - 19 20 21 % Plotting the graph plot([1:25] , timerec , [1:25] , timeloop, [1:25] , timeEqn); xlabel('n') y label('Average time') legend('timerec' 'time loop', 'timeEqn');

22 23 24 25 26 27 28 % Writing recursive code to calculate fibonacci number function nelem = fibrec(n) if(n == 0) nelem = 0; elseif(n == 1) nelem = 1; else nelem = fibrecín - 1) + fibrecín - 2); end end 29 - 30 31 32 33 34 35 36 37 38 39 40 41 42 43 - % Writing iterative code function ne lem = fibloop(n) n_second_prev = 0; n_prev = 1; for i = 2:n nelem = n_prev + n_second_prev; n_second_prev = n_prev; n_prev = nelem; end end 0 b 44 b 45 5 46 47 48 % Writing closed form function function ne lem = fibEqn(N) r = (1 + sqrt(5)) / 2; nelem = round(((r^N) ((1 - 1)^N)) / sqrt(5)); end

OUTPUT:

X10-3 4.5 4 timerec timeloop timeEqn 3.5 3 2.5 Average time 2 1.5 1 0.5 0 5 10 15 20 25