The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.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 in Algorithms by Boss (18k points)
edited by | 1.7k views
+8

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$

1 Answer

+25 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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,204 questions
43,662 answers
124,117 comments
42,948 users