(^282) COMPUTATIONAL COMPLEXITY
Figure 6.1: The Tower of Hanoi problem.
from the third peg to the second peg.
Let f(n) be th e number of moves we need to move n disks from one peg
to another peg by this recursive algorithm. Then, f(n) satisfies the following
recursive relation:
f(l) = 1
f(n) = 2f(n - 1) + 1, n 2 2.
It follows easily from this recursion that
f(n) = 2f(n - 1) + 1 = 22f(n - 2) + 2 + 1
- _ .*. = 2n-lf(l) + 2”-2 + l l l + 1 = 2” - 1.
In addition, this is the minimum number of moves required to transfer n
disks from one peg to another. Indeed, to do such a transfer, we must move
the largest disk from one peg to the other. Before this move, we must first
move all other disks to the third disk. Also, after the move of the largest disk,
we must move all other disks to the top of the largest disk. Therefore, the
minimum number g(n) of moves satisfies the following inequality:g(l) =l
g(n) 2 2g(n - 1) + 1, n > - 2.Thus, g(n) > f(n) = 2” - 1.
Finally, 1% us calculate how much time it takes to solve the problem for
n = 64. Suppose that we can move one disk from one peg to another peg in
one second. How long does it take to move the whole tower of 64 disks from
the first peg to the third one? A year has either 365 or 366 days, and a day has
86,400 seconds. Therefore, a year has approximately 31,600,OOO seconds. This
means that we need about (264 - 1)/(31,600,000) B 584,000,000,000 years
to solve this problem. Even if we can build a robot to move one thousand
disks in one second, it would still take 584 million years to solve the problem.
Thus, we can confidently say that the problem is infeasible. qIn the above example, we argued that the Tower of Hanoi problem is infea-
sible for input size n = 64. We note that for small size n = 10, the solution