Climbing Stairs Problem in DSA C - Time & Space Complexity

Time Complexity: Climbing Stairs Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to solve the climbing stairs problem changes as the number of stairs grows.

Specifically, how does the number of steps to calculate ways increase when the stairs increase?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int climbStairs(int n) {
    if (n <= 2) return n;
    int first = 1, second = 2, third = 0;
    for (int i = 3; i <= n; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return second;
}
    

This code calculates how many distinct ways there are to climb n stairs, taking 1 or 2 steps at a time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that runs from 3 to n.
• How many times: It runs (n - 2) times, once for each stair from 3 up to n.

How Execution Grows With Input

Each new stair adds one more loop iteration, so the work grows steadily as n grows.

Input Size (n)	Approx. Operations
10	8 (loop runs 8 times)
100	98 (loop runs 98 times)
1000	998 (loop runs 998 times)

Pattern observation: The number of operations grows linearly with the number of stairs.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the number of ways grows in direct proportion to the number of stairs.

Common Mistake

[X] Wrong: "Because the problem involves Fibonacci numbers, the time complexity is exponential."

[OK] Correct: This code uses a simple loop and stores only needed values, so it runs in linear time, not exponential.

Interview Connect

Understanding this problem's time complexity shows you can spot efficient solutions and avoid slow recursive traps, a key skill in interviews.

Self-Check

"What if we changed the code to use simple recursion without memoization? How would the time complexity change?"