fibonacci.md

This is uncached. It has O(2^n) time complexity.

def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)

We can pretty easily make this O(n) by introducing a caching decorator.

def memoize(f):
    cache = {}
    def g(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return g

Now, we decorate our fib() function and it works in O(n) time (and space) complexity.

@memoize
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)