Towers of Hanoi solution better than O(2^n)?

Question

Is there a solution for Towers of Hanoi whose running time is less than O(2n) where n is the number of disks to move? My solution takes O(2n) time. Also, the below solution is with recursion. Can we use Dynamic Programming with the concept of memoization to solve this in a lesser time? ``` public void towersOfHanoi( int num, MyStack from, MyStack to, MyStack spare ) { if (num == 1) { int i = from.pop(); to.push(i); System.out.println("Move "+i+" from "+from.getName()+" to " + to.getName()); return; } towersOfHanoi(num - 1, from, spare, to); towersOfHanoi(1, from, to, spare); towersOfHanoi(num - 1, spare, to, from); } ``` `MyStack` is an extended version of `Stack` class in Java that adds a `name` field and accessor. Also, are there any variations of the same problem?

Accepted Answer

Given that solving Towers of Hanoi always takes 2^n - 1 steps...no, you're not going to find a faster algorithm, because it takes O(2^n) just to print out the steps, much less compute them.

Towers of Hanoi solution better than O(2^n)?

Solution

Problem