Exponential computation time of naive Fibonacci algorithm

gen_fibonacci_plots.py

from time import time
from typing import List
import numpy as np
from scipy.optimize import curve_fit
import matplotlib.pyplot as plt


def fibonacci_naive(n: int) -> int:
    if n <= 2: return 1
    return fibonacci_naive(n-1) + fibonacci_naive(n-2)


def fibonacci(n):
    table = [1, 1]

    while len(table) < n:
        table.append(table[-1] + table[-2])

    return table[-1]


def get_fibonacci_times(max_n: int, cache=True) -> List[int]:
    times = []

    for i in range(int(max_n / 100)):
        start = time()
        if cache: fibonacci(i * 100)
        else: fibonacci_naive(i)
        times.append(time() - start)

    return times


def main():
    times = get_fibonacci_times(35, cache=False)
    print(times)
    times = get_fibonacci_times(100000, cache=True)
    print(times)


if __name__ == '__main__':
    main()