Fibonacci functions: An Overview of Algorithmic Complexity

fib.py

# This guy runs in linear O(n) time. That is good but its somewhat complex
def fib(n):
    if n == 0 or n == 1:                     # 1
        return 1
    
    lastNum = 1                              # 1
    currentNum = 1                           # 1
    idx = 1                                  # 1
    
    for i in range(n - 1):                   # 1
        newNum = lastNum + currentNum        # n - 1
        lastNum = currentNum                 # n - 1
        currentNum = newNum                  # n - 1
        
    return currentNum                        # 1

# This guy is recursive which looks pretty but executes in factorial O(n!). Yikes!
def fib_2(n):
    """Get the nth fibonacci number"""
    
    if n == 0 or n == 1:                     # 1
        return 1
    
    return fib_2(n - 1) + fib_2(n - 2)      # 1

def memoize(func):
    cache = {}
    
    def memoized(*args):
        if args in cache:
            return cache[args]
        
        result = func(*args)
        cache[args] = result
        
        return result
    
    return memoized

# Memoization cuts this down to O(n) time. Nice!!!
fib_3 = memoize(fib_2)

print(fib(10))
print(fib_2(10))
print(fib_3(10))