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.
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
- 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
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.