Recursive Algorithm and Complexity Analysis of Tower of Hanoi

A recursive algorithm is like solving a big problem by cutting it into smaller and smaller copies of the same problem. You keep doing this until the problem becomes so small that it is very easy to solve. This smallest and easiest version is called the base case. After solving it, you combine all the small answers to get the final big answer.

The Tower of Hanoi is a puzzle that can be solved using recursion. There are three pegs and some disks of different sizes. All the disks start on one peg, arranged from biggest at the bottom to smallest at the top. The aim is to move all the disks to another peg. The rules are: you can only move one disk at a time, and you cannot put a bigger disk on top of a smaller one. To solve it, we break the problem into smaller steps — move fewer disks first, then move the biggest disk, and then move the smaller ones again. By repeating this process, the puzzle becomes easier until it is solved completely.

Read Here : Tower of Hanoi Program and Algo in details

Steps to Solve Tower of Hanoi Using Recursion

• Move the top n−1 disks from the source peg to the helper (auxiliary) peg.
• Move the biggest disk (nth disk) from the source peg to the destination peg.
• Move the n−1 disks from the helper peg to the destination peg.

Recursive Algorithm to solve Tower Of Hanoi Puzzle

START
 Procedure TOH(disk, source, dest, aux)
 IF disk == 1, THEN
       move disk from source to dest             
    ELSE
       TOH(disk - 1, source, aux, dest)     // Step 1
       moveDisk(source to dest)          // Step 2
       TOH(disk - 1, aux, dest, source)     // Step 3
    END IF
 END Procedure
 STOP

Complexity Analysis of Tower Of Hanoi

The Tower of Hanoi puzzle has a complexity of O(2ⁿ). This means, with each extra disk, the steps double. First, solving it takes longer with more disks. Also, this growth is exponential, making the puzzle much harder as you add disks. Lastly, even though it seems simple, the puzzle quickly becomes complex.

• Moving n-1 disks from source to aux means the first peg to the second peg (in our case). This can be done in T (n-1) steps.
• Moving the nth disk from source to dest means a larger disk from the first peg to the third peg will require 1 step.
• Moving n-1 disks from aux to dest means the second peg to the third peg (in our example) will require again T (n-1) step.

So, total time taken T (n) = T (n-1)+ 1 + T(n-1)

Our Equation will be

T(n) = 2T(n-1) + 1

T(n) = 2T(n-1) + 1 ———- (1)

after putting n = n-1 in eq 1, Equation will become

T(n-1) = 2T(n-2) + 1 ———— (2)

after putting n = n-2 in eq 1, Equation will become

T(n-2) = 2T(n-3) + 1 ———— (3)

Put the value of T(n-2) in the equation–2 with help of equation-3

T(n-1) = 2T(2T(n-3) + 1) + 1

Put the value of T(n-1) in equation-1 with help of equation-4

T(n) = 2(2(2T(n-3)+1)+1)+1

T(n) = 2³T(n-3) + 2² + 2¹ + 1

After Generalization

T(n) = 2^k T(n-k) + 2^(k-1) + 2^(k-2) + ………. + 2² + 2¹ + 2⁰

From our base condition T(1) =1

n – k = 1
k = n-1

Now put k = n-1 in above equation

T(n) = 2^(n-1) T(n-(n-1)) + 2^(k-1) + 2^(k-2) + ………. + 2² + 2¹ + 2⁰

T(n) = 2^(k)(1) + 2^(k-1) + 2^(k-2) + ………. + 2² + 2¹ + 2⁰

It is in a GP with Common ratio r = 2

First term, a=(2⁰).1

Sum of G.P. = Sn = a(1-rⁿ) / (1-r)

T(n) = 1.(1-2⁽ⁱ⁺¹⁾)/(1-2)

T(n) = 2⁽ⁱ⁺¹⁾ – 1

From the above equation

T(n) = 2^(n-1+1) – 1

T(n) = 2ⁿ – 1 (this is the equation which will give the number of disk movement is required )

Time Complexity of Tower Of Hanoi

The number of moves required to solve the Tower of Hanoi forms a geometric progression (GP): T(n)=1+2+4+⋯+2n−1

The sum of this GP is: T(n)=2n−1

So, the time complexity is:

T(n)=O(2ⁿ−1)

Or simply, we can write:

Time Complexity=O(2ⁿ)

This means the number of moves grows exponentially with the number of disks, making the puzzle much harder as n increases.