Recursive Algorithm and Complexity Analysis of Tower of Hanoi

by

The Tower of Hanoi is a mathematical Puzzle that consists of three towers(pegs) and multiple disks. Initially, all the disks are placed on one rod. And these disks are arranged on one over the other in ascending order of size.

Read Here : Tower of Hanoi Program and Algo in details

Steps to be followed as below

  • Step 1 − Move n-1 disks from source to aux
  • Step 2 − Move nth disk from source to dest
  • Step 3 − Move n-1 disks from aux to dest

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^n). 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^3T(n-3) + 2^2 + 2^1 + 1

After Generalization

T(n) = 2^k T(n-k) + 2^(k-1) + 2^(k-2) + ………. + 2^2 + 2^1 + 2^0

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^1 + 2^0

T(n) = 2^(k)(1) + 2^(k-1) + 2^(k-2) + ………. + 2^2 + 2^1 + 2^0

It is in a GP with Common ratio r = 2

First term, a=(2^0).1

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

T(n) = 1.(1-2^(i+1))/(1-2)

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

From the above equation

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

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

Time Complexity of Tower Of Hanoi

It is a GP series, and the sum is 2^n – 1

T(n)= O( 2^n – 1) , or We can say time complexity is O(2^n) which is exponential.