The Fabonacci series (named after the lesser know cousin of Fibonacci) is a) Sho
ID: 3661693 • Letter: T
Question
The Fabonacci series (named after the lesser know cousin of Fibonacci) is
a) Show in pseudo code an exponential algorithm to solve this for an arbitrary integer n. As a function of n give a rough big O complexity class for the algorithm and justify your answer.
b) Show in psuedocode a linear algorithm to solve this for an arbitrary integer n. As a function of n give the exact number of adds and multiplies necessary for your algorithm to calculate f(n).
/n)-fin-1) +/n-2) *fin-3) for integer n > 2 withf(0) (1)-K2)-1Explanation / Answer
a) pseudocode fibonacci(n)
if(n=0||n=1||n==2)
return 1
else
return fibonacci(n-1)+fibonaccci(n-2)*fibonacc(n-2)
In the above multiy way recursive function the time complexity grows exponentially complexity is O(n3)
b)linear algorithm:
Fibonacci(n)
Inital values: sum=0,i=3,a=1,b=1,c=1;//i=3 because we have f(0),f(1) and f(2) values.
while(i<n)
sum=sum+a+b*c;
b=a;
c=b;
a=sum
end while.
return sum.
End.
This while loop calculates nth fibonacci number with a time complexity of O(n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.