Skip to main content

Don't Be Fooled By The Simplicity

Posted by mortazavi on August 4, 2005 at 7:00 AM PDT

When describing and praising recursive algorithms, I gave an example for solving the Tower of Hanoi puzzle. The curious among you may have done a simple, back of the envelope, complexity analysis. It turns out that the time complexity of the algorithm is exponential. It is order of 2 ^ n.

In the real world, a puzzle of 64 disks will take 584 billions years to solve the puzzle if the priest takes 1 second to move 1 of the disks from one peg to another. Adding more priests won't make a difference here other than attending to the priests' needs to sleep.

So, what looks simple on the surface may take a long time to complete.

By the way, I just noticed the comments to my earlier post. I think the comments discuss the problem wonderfully on their own. At their core, they also show what happens when a specific machine's implementation of recursive algorithms play time and space against each other.