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.

Page Contents

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