You've successfully subscribed to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 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
``````
Algorithm

### Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.