+20 votes
2.7k 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 − 1) + n$
3. $T (n) = 2T(n/2) + 1$
4. $T (n) = 2T(n − 1) + 1$
asked
edited | 2.7k views
+19

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$

0
this should be the best answer.👍

## 2 Answers

+27 votes
Best answer

Recurrence relation for Towers of Hanoi is

$T(1) = 1$

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

So Answer should be (D)

answered by (421 points)
edited by
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.

answered by Active (1.5k points)
Answer:

+19 votes
4 answers
1
+3 votes
3 answers
2
+16 votes
5 answers
3
+12 votes
3 answers
4
+18 votes
2 answers
5
+19 votes
4 answers
6
+18 votes
1 answer
7