Tower of Hanoi Problem in DSA Typescript - Time & Space Complexity

Time Complexity: Tower of Hanoi Problem

O(2^n)

Understanding Time Complexity

We want to understand how the time needed to solve the Tower of Hanoi grows as we add more disks.

The question is: How does the number of moves increase when the number of disks increases?

Scenario Under Consideration

Analyze the time complexity of the recursive Tower of Hanoi function below.

function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}
    

This code moves n disks from one peg to another using recursion and an auxiliary peg.

Identify Repeating Operations

Look at what repeats in the code:

• Primary operation: Recursive calls that move smaller stacks of disks.
• How many times: Each call makes two smaller recursive calls plus one move operation.

How Execution Grows With Input

When we add one more disk, the number of moves roughly doubles and then adds one more move.

Input Size (n)	Approx. Operations (Moves)
1	1
2	3
3	7
4	15
5	31

Pattern observation: The moves grow exponentially, doubling each time plus one extra move.

Final Time Complexity

Time Complexity: O(2^n)

This means the time needed doubles with each additional disk, growing very fast as n increases.

Common Mistake

[X] Wrong: "The time grows linearly because we just move each disk once."

[OK] Correct: Each disk move depends on moving smaller stacks multiple times, so moves multiply, not just add up.

Interview Connect

Understanding this problem helps you think about recursion and exponential growth, which are common in many coding challenges.

Self-Check

"What if we changed the problem to move disks iteratively instead of recursively? How would the time complexity change?"