1

For this problem, we are given a function f which calculates the nth fibonacci number in the standard way:

f(n)
 {
  if(n == 0)
   return 0;
  if(n == 1)
   return 1;
  else return f(n-1) + f(n-2);
 }

I am then tasked with calculating the number of arithmetic operations performed by the function on an input n. I know that each call to f performs 3 operations (2 minus, 1 addition) and I've then attempted to find it by expanding the function to try and find some sort of recurrence relation and then working out how many arithmetic operations get done. But then I get stuck because this doesn't come out as the right answer.

The correct answer is f does 3f(n+1)-3 arithmetic operations on an input n. Please could someone explain this to me? It is important as we are later asked to find the time complexity using this as a starting point.

Thanks very much, Niamh

Niamh Akerman
  • 13
  • 4
  • You might want to check [this](http://stackoverflow.com/a/360773/1083314) answer out. It attempts to inductively calculate the time complexity of calculating the nth number in fibonacci series. – Vivek Pradhan Nov 27 '14 at 06:54

2 Answers2

2

Time complexity of your algorithm is close to 2^(n) . Hence it is O( 2^n ) Here is an example of how your algorithm will solve if n = 6

Working of fibonacci

You algorithm does T(n) = T(n-1) + T(n-2) + O(1) .

T(n-1) = T(n-2) + T(n-3) + O(1)

T(n-2) = T(n-3) + T(n-4) + O(1)

. . .

T(2) = T(1) + T(0) + O(1)

Have a look at Fibonacci time complexity

T(n) = T(n-1) + T(n-2) + O(1) which is equal to

T(n) = O(2^(n-1) ) + O(2^(n-2) )+ O(1) = O(2^n)

Community
  • 1
  • 1
Shankar
  • 417
  • 1
  • 6
  • 17
0

perhaps n/2 times additon operations performed ;

for(i=3;i<=n;i++)
let n=4;
variable a,b=0,c=1;
[a=b+c;b=c;c=a;].........(1) //now a=1;b=1;c=1;
[a=b+c,b=c,c=a)...............(2) //now a=2;b=1;c=2;

output:0112.
Note:if n is Odd No then addition operation performed (n/2)+1 times;
Note:if n is Even No then addition operation performed (n/2) times;

!Please correct me if i am wrong!

pawan poddar
  • 1
  • 1