Programming challenges: Nth Fibonacci

nth-fibonacci.py

# O(n) time | O(n) space
def getNthFib(n):
    memo = {1: 0, 2: 1} # start of with initial values in cache
    if n in memo:
        return memo[n]
    else:
        memo[n] = calcFib(n) # store result in cache
        return memo[n]

# O(n) time | O(1) space
def calcFib(n):
  # Gets called exponentially and adds the result of each call
    return getNthFib(n - 1) + getNthFib(n - 2)
  
def getNthFib(n):
    # Write your code here.
    # [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ]
    
    sequence = [0, 1]
    if n <= 2: return sequence[n - 1]
    
    result = 0
    for idx in range(3, n + 1): # start from 3rd fibonacci number
        result = sum(sequence)
        sequence[0] = sequence[1]
        sequence[1] = result
    return result