edited by
15,481 views
35 votes
35 votes

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 − 1) + n$
  3. $T (n) =  2T(n/2) + 1$
  4. $T (n) =  2T(n − 1) + 1$
edited by

3 Answers

Best answer
38 votes
38 votes

Recurrence relation for Towers of Hanoi is

$T(1) = 1$

$T(n) = 2 T( n-1 ) +1$

So Answer should be (D)

edited by
6 votes
6 votes

Ref: https://www.hackerearth.com/blog/developers/tower-hanoi-recursion-game-algorithm-explained/

For a given N number of disks, the way to accomplish the task in a minimum number of steps is:

  1. Move the top N−1 disks to an intermediate tower. (Look at the first 3 steps in the figure) 
  2. Move the bottom disk to the destination tower.(Look at the 4th step in the figure)
  3. Finally, move the N−1 disks from the intermediate peg to the destination tower.(Look at the last 3 steps in the figure)

TOH (N=3,L,M,R)
{
  if(N==0)
    return;
  else {    
      TOH(N-1,L,R,M)
      MOVE(L-R)
      TOH(N-1,M,L,R)}
}

$T(N)=2T(N-1)+1$

0 votes
0 votes

Following are the steps to follow to solve Tower of Hanoi problem recursively.

Let the three pegs be A, B and C. The goal is to move n pegs from A to C.
To move n discs from peg A to peg C:
    move n-1 discs from A to B. This leaves disc n alone on peg A
    move disc n from A to C
    move n?1 discs from B to C so they sit on disc n

The recurrence function T(n) for time complexity of the above recursive solution can be written as following.

T(n) = 2T(n-1) + 1, Hence D is the right answer.

Answer:

Related questions

42 votes
42 votes
4 answers
1
9 votes
9 votes
4 answers
2
gatecse asked Sep 29, 2014
2,662 views
Given the sequence of terms, $\text{AD CG FK JP}$, the next term is$\text{OV}$$\text{OW}$$\text{PV}$$\text{PW}$
13 votes
13 votes
1 answer
3
gatecse asked Sep 29, 2014
2,795 views
Which one of the following options is the closest in meaning to the word given below?Mitigate DiminishDivulgeDedicateDenote
10 votes
10 votes
2 answers
4
gatecse asked Sep 29, 2014
2,938 views
Choose the most appropriate alternative from the options given below to complete the following sentence:Despite several _________ the mission succeeded in its attempt to ...