Climbing Stairs Problem in DSA Typescript - 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 many steps does the program take to find the total ways to climb?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let first = 1, second = 2;
  for (let i = 3; i <= n; i++) {
    const 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 up to n.
• How many times: It runs (n - 2) times, once for each stair from 3 to n.

How Execution Grows With Input

Each new stair requires one addition and two variable updates inside the loop.

Input Size (n)	Approx. Operations
10	8 additions and updates
100	98 additions and updates
1000	998 additions and updates

Pattern observation: The number of operations grows roughly in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Because the problem involves Fibonacci numbers, it must take exponential time."

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

Interview Connect

Understanding this problem helps you practice turning recursive ideas into efficient loops, a skill often needed in interviews.

Self-Check

"What if we changed the problem to allow steps of 1, 2, or 3 at a time? How would the time complexity change?"