The fibonacci sequence is defined by F(n) = F(n-1) + F(n-2), where F(1) = 1 and F(0) = 0. The naive solution (recursive) is quite obvious, but has a runtime of O(2^n) which is bad. Is there a way that you can calculate the sequence in a shorter time?

There are more efficient ways to calculate the fibonacci sequence, some a variation of dynamic programming.

# Fibonacci Series using Dynamic Programming
def fibonacci(n):
# Taking 1st two fibonacci nubers as 0 and 1
f = [0, 1]
for i in range(2, n+1):
f.append(f[i-1] + f[i-2])
return f[n]

Another dynamic approach

# Initialize array of dp
dp = [-1 for i in range(10)]
def fib(n):
if (n is less than or equal to 1):
return n;
global dp;
# Temporary variables to store
# values of fib(n-1) & fib(n-2)
first = 0;
second = 0;
if (dp[n - 1] != -1):
first = dp[n - 1];
else:
first = fib(n - 1);
if (dp[n - 2] != -1):
second = dp[n - 2];
else:
second = fib(n - 2);
dp[n] = first + second;
# Memoization
return dp[n] ;

More optimized

# function that returns nth
# Fibonacci number
def fib(n):
F = [[1, 1],
[1, 0]]
if (n == 0):
return 0
power(F, n - 1)
return F[0][0]
def multiply(F, M):
x = (F[0][0] * M[0][0] +
F[0][1] * M[1][0])
y = (F[0][0] * M[0][1] +
F[0][1] * M[1][1])
z = (F[1][0] * M[0][0] +
F[1][1] * M[1][0])
w = (F[1][0] * M[0][1] +
F[1][1] * M[1][1])
F[0][0] = x
F[0][1] = y
F[1][0] = z
F[1][1] = w
# Optimized version of
# power() in method 4
def power(F, n):
if( n == 0 or n == 1):
return;
M = [[1, 1],
[1, 0]];
power(F, n // 2)
multiply(F, F)
if (n % 2 != 0):
multiply(F, M)

Even more optimized

# Python3 program to find n'th
# fibonacci Number
import math
def fibo(n):
phi = (1 + math.sqrt(5)) / 2
return round(pow(phi, n) / math.sqrt(5))