AlgorithmComplexity

3. Algorithm

---

ALGORITHM: Towers(n, from, to, aux)

//tower of Hanoi uses three pegs source, destination and auxiliary fro movement of //disks and

//pegs are named as A ,B,C.

//Input: A Positive Decimal Number N

//OUTPUT: The Movement of disks from SOURCE peg to DESTINATION peg

1. If(n=1)
   Output the SOURCE and DESTINATION peg
   Return
   End of if

2. Move top n-1 disks from A to B using C as auxiliary
   Towers(n-1,from, aux, to)

3. Output the SOURCE and DESTINATION peg

4. Move n-1 disk from B to C using A as auxiliary
   Towers(n-1,aux,to,from)
   End of towers

We see above, this is a recursive algorithm .To move n (n>1) disks from peg1 to peg3 with peg 2 as auxiliary, we first move recursively n-1 disks from peg1 to peg 2 with peg 3 as auxiliary then move the largest disk directly from peg 1 to peg 3 and finally move recursively n-1 disks from peg2 to peg3 using peg1 as auxiliary. Of course if n=1, we can simply move the single disk directly from the source peg to the destination peg.

---

4. Complexity

---

Complexity of the above algorithm depends on the number of disk movements. Hence the complexity is a function of ‘n’, the number of disks given as input to the algorithm.

Now the number of disk moves which depends only on ‘n’ can be defined recursively as
M(n) = M(n-1) + 1+ M(n-1) for n>1

With the obvious condition M(1) = 1, we have the following complete recursive relation given below for number of moves M(n):
M(n) = 2M(n-1) + 1 for n>1
M(1) = 1.

We solve this relation by method of backward substitution to get
M(n) = 2n-1

Thus we have an exponential algorithm.

Home