title: Complexity for towers of Hanoi?
body: <p>I was recently solving Towers of Hanoi problem. I used a "Divide and Conquer" Strategy to solve this problem. I divided the main problem into three smaller sub problems and thus following recurrence was generated.</p>
  
  <blockquote>
    <p>T(n)=2T(n-1)+1</p>
  </blockquote>
  
  <p>Solving this leads to</p>
  
  <blockquote>
    <p>O(2^n) [exponential time]</p>
  </blockquote>
  
  <p>Then i tried to use memoization technique to solve it, but here too the space complexity was exponential and heap space exhausted very soon and problem was still unsolvable for larger n.</p>
  
  <p>Is there a way to solve the problem in less than exponential time? What is the best time in which the problem can be solved?</p>