Algorithm function for fibonacci series

Question

I'm not looking necessarily for an answer, but I am looking for what this question is asking of. Found this question studying for an interview but not sure what they're asking?

Write function that runs through the Fibonacci sequence and returns the index that is passed in as a parameter.

Answer 1

firstly,you can update your base math information about Fibonacci with this link from wiki. and look at this formula for fast calculate.and you can read all of about it in this link.

This is recursive function to compute nth Fibonacci number and is of O(2^n) time:

 int Fibonacci(int n) {  
        if (n == 0 || n == 1)  return n;
        else
        return Fibonacci(n - 1) + Fibonacci(n - 2); }

Computing the Sequence

You might argue that in terms of actually computing the values of the Fibonacci sequence on a computer, you’re better off using the original recurrence relation, f[n]=f[n−1]+f[n−2]. I’m inclined to agree. To use the direct closed-form solution for large n, you need to maintain a lot of precision. Even with 9 decimal places out, fn≈round(0.723606798⋅(1.618033989)n), for example, is only valid for up to n=38 (observe here versus here). Also, adding integers is much less computationally expensive and more precise than exponentiating a symbolic fraction or a floating point value

this is better idea to compute nth Fibonacci number and is of O(n) time:

int Fibonacci(int n) { 
if(n <= 0) return 0;
if(n > 0 && n < 3) return 1;

int result = 0;
int preOldResult = 1;
int oldResult = 1;

for (int i=2;i<n;i++) { 
    result = preOldResult + oldResult;
    preOldResult = oldResult;
    oldResult = result;
}

return result;}

and this is the best way to compute nth Fibonacci number and is of O(log(n)) time:

this link:

As you are already suspecting, this will work very similar. Use the n-th power of the x * x matrix

|1 0 0 0  .... 1 1|
|1 
|  1
|    1
|      1
|        1
...................
...................
|          ... 1 0|

This is easy to understand if you multiply this matrix with the vector

f(n-1), f(n-2), ... , f(n-x+1), f(n-x)

which results in

f(n), f(n-1), ... , f(n-x+1)

Matrix exponentiation can be done in O(log(n)) time (when x is considered to be constant).

For the Fibonacci recurrence, there is also a closed formula solution, see here http://en.wikipedia.org/wiki/Fibonacci_number, look for Binet's or Moivre's formula.

and look at: 1-nth fibonacci number in sublinear time