java - big-o order of recursive and iterative fib functions? -

i asked write fib function in efficient manner?

this implementation provided:

public static int fib(int n) {     int prev1 = 1, prev2 = 1, ans = 1, = 3;      while (i <= n)     {         ans = prev1 + prev2;         prev1 = prev2;         prev2 = ans;         i++;     }     return ans; } 

is efficient? big-o order?

i asked give big-o notation of recursive implementation:

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

i think 1 exponential 2^n why it's inefficient.

i best way find fib particular n using matrix calculation method given in link - page19

where f0 = 0 , f1 = 1. matrix relation can easlily used find fib value of n , n+1. best part is multiplying matrix need not mutliplied n times logn times find actual value of multiplier. overall compleixty of algorithm o(logn).

the equation derived basic relation of

f1 = 0*f0 + 1*f1

f1 = 1*f0 + 1*f2

iterating on n multiplier matrix has multiplied n times.