Today seems to be an algorithms-appreciation day. I coded up two versions of generating the nth Fibonacci sequence. The naive one we all learn in class with an O(2^n) run time:
And then a more efficient algorithm that memoizes– run time of O(n):