# Time(n) Complexity of Fibonacci Algorithms

It is my first use of classes in Python. I wanted to create something useful and try some new things as I learn this cool language: strategy pattern, testing with nanoseconds precision, curve/poly fitting, and making a graphic presentation. The budget was 150 lines of code: 50 for five Fibonacci number calculations, 50 for testing and checking the results, 50 for presentation. PyCharm was my mentor and strict format enforcer: 22 blank lines. I made it in 149 lines and then added one comment line. Could be a better “curve fit” and “poly fit” string formulas, but it will force me to go over 150 lines.

Here is what this program does:

1. Calculates Fibonacci numbers from 2 to 30 by five different methods. Tests if all methods produce the same results and keep the shortest runtime from 10 tries.
2. Plots all best times in nanoseconds at four subplots: regular axes, log Y, zoom to 30000 nSec, and zoom+ to 3000 nSec.
3. It uses curve_fit from scipy and polyfit from numpy to find the best parameters for math formulas describing the time complexity of these Fibonacci algorithms.

I was happy to see the recursion as (446 * 1.62 ** n) just after the first tests and bug fixing - that is a theoretical O(φ**n) or 1.6180339887…

Critique and suggestion on how to write a better code are welcome.

Should I put all import statement at the top?

Here is the code:

from abc import ABCMeta, abstractmethod
from cachetools import cached, TTLCache

class Fibonacci(metaclass=ABCMeta):  # Abstract prototype ######################
def fibonacci(self, n):
if isinstance(n, int) and n >= 0:
return self._fibonacci(n) if n >= 2 else [0, 1][n]
raise ValueError

@abstractmethod
def _fibonacci(self, n):
pass

class FibonacciRecursion(Fibonacci):  # 1. Classic and also naive computation ##
def _fibonacci(self, n):
return self.fibonacci(n - 1) + self.fibonacci(n - 2)

class FibonacciCacheTools(Fibonacci):  # 2. The cache fixes bad algorithm choice
cache = TTLCache(maxsize=1500, ttl=3600)

@cached(cache)
def _fibonacci(self, n):
return self.fibonacci(n - 1) + self.fibonacci(n - 2)

class FibonacciAddition(Fibonacci):  # 3. It is O(n), not O(2**n) as before ####
def _fibonacci(self, n):
f0, f1 = 0, 1
for _ in range(1, n):
f0, f1 = f1, f0 + f1
return f1

def __init__(self):
self._n = 2
self._f0 = 1
self._f1 = 1

def _fibonacci(self, n):
if n == self._n:
return self._f1
if n < self._n:
self.__init__()
for _ in range(self._n, n):
self._f0, self._f1 = self._f1, self._f0 + self._f1
self._n = n
return self._f1

class FibonacciFormula(Fibonacci):  # 5. Formula of Binet, Moivre, and Bernoulli
# Exact integer until Fibonacci(71)
# Float error at Fibonacci(1475)  OverflowError: (34, 'Result too large')
S5 = 5.0 ** 0.5  # Square root of 5

def _fibonacci(self, n):
phi = (1.0 + FibonacciFormula.S5) / 2.0  # φ Python speaks greek!
psi = (1.0 - FibonacciFormula.S5) / 2.0  # ψ PyCharm doesn't like it ;-(
return int((phi ** n - psi ** n) / FibonacciFormula.S5)

if __name__ == '__main__':  # Testing ... ######################################
import platform
import time
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import curve_fit

def func1(x, a, b):  # function to fit exponential Fibonacci
return '%f * %f**x' % (a, np.exp(b)) if x is None else a*np.exp(b*x)

def func2(x, a, b, c):  # function to fit with cubic curve
return '%f + %f*x + %f*x**2' % (a, b, c) if x is None else a+x*(b+c*x)

def first_test(fibonacci_max, repeat):  # Collect times, curve fit, and plot
methods = [  # Function to test, color, poly fit, curve fit
[FibonacciRecursion(),    'blue',   2, func1],
[FibonacciCacheTools(),   'orange', 1, func2],
[FibonacciFormula(),      'purple', 1, func2],
]
print('Number,Fibonacci,Times for all methods in nanoseconds')
n_max = fibonacci_max - 1  # we start from n=2 (0, 1 - the same time)
y = [[0 for _ in range(n_max)] for _ in methods]
for j in range(n_max):  # Run tests and collect times in array y #######
n = j + 2
old = None
for i, method in enumerate(methods):
best = None
for k in range(repeat):
start = time.perf_counter_ns()
result = method.fibonacci(n)
stop = time.perf_counter_ns()
duration = stop - start
if best is None or duration < best:
best = duration
if old is None:
old = result
elif result != old:
print(
'Error: different results %d and %d for function %s'
' F(%d) in call # %d,' %
(old, result, method.fibonacci.__name__, n, k+1))
exit(1)
if i == 0:
print(n, ',', old, sep='', end='')
print(',', best, sep='', end='')
y[i][j] = best
print()
plt.figure(1)  # Start plotting ########################################
plt.suptitle('Time(n) Complexity of Fibonacci Algorithms. n = 2,3,...,'
'%d,%d' % (n_max, fibonacci_max))
x = np.array([i + 2 for i in range(n_max)])
for i in range(4):
plt.subplot(221 + i)
for j, m in enumerate(methods):
s = str(m.__class__.__name__)[len('Fibonacci'):]
plt.plot(x, y[j], 'tab:' + m, label=s)
plt.title(['time in nanoseconds', 'log(Time)', 'zoom', 'zoom+'][i])
plt.grid(True)
if i == 0:
plt.legend()
elif i == 1:
plt.semilogy()
else:
x_min, x_max, _, _ = plt.axis()
plt.axis([x_min, x_max, 0.0, 30000.0 if i == 2 else 3000.0])
for i, m in enumerate(methods):  # Curve and poly fitting ##############
plt.figure(2 + i)
name = str(m.__class__.__name__)[len('Fibonacci'):]
plt.plot(x, y[i], 'ko', label=name)
c, _ = curve_fit(m, x, y[i])
c_name = 'curve fit:' + m(None, *c)
plt.plot(x, m(x, *c), 'y-', label=c_name)
p = np.poly1d(np.polyfit(x, y[i], m))
p_name = 'poly fit: ' + str(p)
plt.plot(x, p(x), m, label=p_name)
plt.legend()
print('%s\n%s\n%s\n' % (name, c_name, p_name))
plt.show()

print('Python version  :', platform.python_version())
print('       build    :', platform.python_build())
print('       compiler :\n', platform.python_compiler())
first_test(fibonacci_max=30, repeat=10)


The output:

\$ python fibonacci.py
Python version  : 3.7.3
build    : ('v3.7.3:ef4ec6ed12', 'Mar 25 2019 16:52:21')
compiler :
Clang 6.0 (clang-600.0.57)
Number,Fibonacci,Times for all methods in nanoseconds
2,1,1027,2598,731,526,874
3,2,1638,2516,769,523,956
4,3,2818,2470,806,532,904
5,5,4592,2413,840,526,902
6,8,7571,2531,936,562,955
7,13,12376,2490,909,538,999
8,21,20528,2588,972,551,973
9,34,33349,2628,1074,581,1037
10,55,60107,2782,1116,581,997
11,89,85465,2421,1056,534,939
12,144,137395,2429,1101,534,942
13,233,222623,2411,1136,539,955
14,377,360054,2476,1216,551,938
15,610,600066,2736,1332,563,1006
16,987,971239,2529,1323,541,937
17,1597,1575092,2479,1359,552,937
18,2584,2565900,2632,1464,563,962
19,4181,4071666,2583,1485,555,953
20,6765,6630634,2503,1481,532,914
21,10946,10843455,2527,1571,522,930
22,17711,18277770,2617,1646,548,952
23,28657,28838223,2620,1739,573,967
24,46368,47167582,2481,1713,543,932
25,75025,77326177,2481,1709,531,909
26,121393,126154837,2587,1799,546,944
27,196418,205083621,2527,1857,548,942
28,317811,329818895,2444,1822,531,952
29,514229,533409650,2493,1932,551,946
30,832040,866064386,2509,1967,553,947
Recursion
curve fit:448.753271 * 1.619991**x
poly fit:            2
1.751e+06 x - 4.225e+07 x + 1.829e+08

CacheTools
curve fit:2492.458456 + 7.778994*x + -0.252776*x**2
poly fit:
-0.3099 x + 2539

curve fit:636.162562 + 42.475661*x + 0.074421*x**2
poly fit:
44.86 x + 622.3

curve fit:528.372414 + 2.642894*x + -0.076063*x**2
poly fit:
0.2089 x + 542.5

Formula
curve fit:920.230213 + 5.076194*x + -0.163003*x**2
poly fit:
-0.1399 x + 950.5 • Welcome to Code Review! Well done on presenting intent and constraints upfront. One thing nagging me: why not choose an argument range to try and push the limits of integer representations (somehow managing run time of the plain recursive approach (and checking for deviation of "the formula result")). – greybeard Apr 2 at 5:58
• Thank you for the welcome and the comment. Actually, I did comment the line with "[FibonacciRecursion(), 'blue', 2, func1]," and "elif result != old:" in order to push the limit and see what will happen next: they stay steady flat O(1) except Addition O(n). Also started to write another test program to see the error in "the formula result" and a possibility to compensate it: the absolute error starts almost as another Fibonacci from 72 with F(n-71) range, but the relative error has a linear grow from 2.0e-15 at F(72) to 4.4e-14 at F(1314). – Alex Lopatin Apr 2 at 8:51