2,029 views

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$

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.

1
825 views