NIELIT 2016 DEC Scientist B (IT) - Section B: 16

Question

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs is:

• A. $T(n)=2T(n-2)+2$
• B. $T(n)=2T(n/2)+1$
• C. $T(n)=2T(n-1)+n$
• D. $T(n)=2T(n-1)+1$

Answer 1

TOH(n, x, y, z)
{
   if (n >= 1)
   {
      // put (n-1) disk to z by using y-----------T(n-1)
      TOH((n-1), x, z, y)
   
       // move larger disk to right place-----------------only one disk move at a time.
       move:x-->y
     
      // put (n-1) disk to right place 
      TOH((n-1), z, y, x)-------------T(n-1)
   }
}

  Recurrence relation :   T(n) = 2T(n-1) +1

  Hence option D is correct.