Optimal Fibonnaci

fib.py

# Recursion Method
# O(2n) Time | O(n) Space Complexity
def getFib(n):
	if n == 1:
		return 0
	if n == 2:
		return 1
	return getFib(n-1) + getFib(n-2)

# Recursion with cache method
# O(n) Time | O(n) Space Complexity
def getFib(n, memoize = {1:0, 2:1}):
	if n in memoize:
		return memoize[n]
	else:
		memoize[n] = getN(n-1, memoize) + getN(n-2, memoize)
	   return memoize[n]

# Iterative and most effective method
# O(n) Time | O(1) Space complexity
def getFib(n):

	lastTwo = [0, 1]
	counter = 3

	while counter <= n:
		nextFib = lastTwo[0] + lastTwo[1]
		lastTwo[0] = lastTwo[1]
		lastTwo[1] = nextFib
		counter += 1
	return lastTwo[1] if n > 1 else lastTwo[0]