What is the Big O for Towers of Hanoi algorithm?

6down vote favorite

3

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 memorization to solve this in a lesser time?