CODEWITHSUNDEEP
javaalgorithmbig-ofibonacci
George Denver
George Denver

Reputation: 21

Big O notation for fib recursion

What is the Big-O run-time of the following function? Explain.

static int fib(int n){
  if (n <= 2)
     return 1;
  else 
     return fib(n-1) + fib(n-2)
   }

Also how would you re-write the fib(int n) function with a faster Big-O run-time iteratively? would this be the best way with O(n):

 public static int fibonacci (int n){
 int previous = -1;
 int result = 1;
 for (int i = 0; i <= n; ++i)
 {
 int sum = result + previous;
 previous = result;
 result = sum;
 }
 return result;
}
}

Upvotes: 0

Views: 3556

Answers (1)

waldyr.ar
waldyr.ar

Reputation: 15234

Proof

You model the time function to calculate Fib(n) as sum of time to calculate Fib(n-1) plus the time to calculate Fib(n-2) plus the time to add them together (O(1)).

T(n<=1) = O(1)

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

You solve this recurrence relation (using generating functions, for instance) and you'll end up with the answer.

Alternatively, you can draw the recursion tree, which will have depth n and intuitively figure out that this function is asymptotically O(2n). You can then prove your conjecture by induction.

Base: n = 1 is obvious

Assume T(n-1) = O(2n-1), therefore

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

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

Iterative version

Note that even this implementation is only suitable for small values of n, since the Fibonacci function grows exponentially and 32-bit signed Java integers can only hold the first 46 Fibonacci numbers

int prev1=0, prev2=1;
for(int i=0; i<n; i++) {
  int savePrev1 = prev1;
  prev1 = prev2;
  prev2 = savePrev1 + prev2;
}
return prev1;

Upvotes: 4

Related Questions