Tower of Hanoi Problem in DSA C - 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.

How does the number of moves change when the number of disks increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
        return;
    }
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls that move disks one by one.
• How many times: Each call splits into two smaller calls with n-1 disks, plus one move.

How Execution Grows With Input

Each time we add a disk, the number of moves roughly doubles and 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 with the number of disks because we move each disk once."

[OK] Correct: Actually, disks are moved multiple times in a recursive pattern, causing exponential growth, not just once each.

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 without recursion? How would the time complexity change?"