# Fastest Way to Calculate Fibonacci Sequence

## Question

Construct an algorithm so that the Nth item of Fibonacci Sequence can be found in the shortest time. Definition of Fibonacci Sequence is:

```
f(n) = 0 , when n = 0
f(n) = 1 , when n = 1
f(n) = f(n-1) + f(n-2), when n > 1
```

## Solution

There are many solutions for this, the simplest way is to use recursive function.

```
fibonacci(n)
if n equals 0 then return 0
else if n equals 1 then return 1
else return fibonacci(n-1) + fibonacci(n-2)
```

There is another way actually, through using loops. The time complexity is O(n).

```
fibonacci(n)
if n equals 0 then return 0
else if n equals 1 then return 1
fib_n_minus_2 = 0
fib_n_minus_1 = 1
fib_n = 0
for i equals 2 to n
fib_n = fib_n_minus_1 + fib_n_minus_2
fib_n_minus_2 = fib_n_minus_1
fib_n_minus_1 = fib_n
return fib_n
```