def fibonacci_iter(n):
    """Iterative implementation of fibonacci. O(n) runtime, O(1) space"""
    if n <= 2:
        return 1

    prev_prev_term = 1  # f(k-2)
    prev_term = 1  # f(k-1)
    for k in range(3, n + 1):
        tmp = prev_term
        # f(k) = f(k-1) + f(k-2) => f(k) at current term becomes f(k-1) at next term
        prev_term += prev_prev_term
        # f(k-1) at current term becomes f(k-2) at next term
        prev_prev_term = tmp
    return prev_term