GATE CSE 2012 | Question: 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 − 1) + n$
• C. $T (n) =  2T(n/2) + 1$
• D. $T (n) =  2T(n − 1) + 1$

Comments

There are three towers named as Left, Middle, Right.
Tower Left contains 3 discs in decreasing size from bottom to top.
We have to move these 3 discs from Left tower to Right tower using Middle tower.
step 1: Move 2 discs from Left tower to Middle tower using Right tower. $n-1$ discs
Step 2: Move the remaining disc from Left tower to Right tower. $1-movement$
Step 3: Move 2 discs from Middle tower to Right tower using Left tower. $n-1$ discs

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

---

this should be the best answer.👍

---

Is it still in syllabus ?

 

Answer 1

Recurrence relation for Towers of Hanoi is

$T(1) = 1$

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

So Answer should be (D)

Answer 2

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 $4^{th}$ 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$

Answer 3

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 4

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

Using Master's Method,

Since a = 2 and a > 1,

Therefore, T(n) = 2^(n/1) ..... [where b = 1 and for a > 1, T(n) = Θ(a^(n/b))]

Therefore, T(n) = Θ(2^n), which is the time complexity of Tower of Hanoi.
 

And Correct Option is D) T(n) = 2T(n - 1) +1