Big O Practice: Climbing Stairs

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Variables

• n - number of stairs (the input integer)

Explanation

A single linear loop computing each step from the prior two - **O(n)** time. Only two rolling variables are kept, **O(1)** space. The naive recursive form (without memo) is the classic O(2ⁿ) trap.

More Big O practice problems · Today's daily problem