in DS retagged by
2,029 views
1 vote
1 vote

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

  1. $T(n)=2T(n-2)+2$
  2. $T(n)=2T(n/2)+1$
  3. $T(n)=2T(n-1)+n$
  4. $T(n)=2T(n-1)+1$
in DS retagged by
2.0k views

1 Answer

2 votes
2 votes
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.

Answer:

Related questions