| Home | Sign up! | Projects | Seminars | Research Notes | Today's Lecture | About |

Update Research Note Form
 Course: Research Note Topic: Research Note Description: The Recurrence Relation emerging out of the basic concept of Towers of Hanoi is :

Let Tn be the no. of steps for Towers of Hanoi with 'n' disks.

Tn = Tn-1 + 1 + Tn-1
Tn = 2Tn-1 + 1
Tn = 2 (2Tn-2 + 1) + 1
Tn = 22Tn-2 + 2 + 1
Tn = 22 (2Tn-3 + 1) + 2 + 1
.................
.................
...................
...................
Tn = 2n-1T1 + 2n-2 + ............................ + 22 + 2 + 1
Tn = 1 + 2 + 22 + ........................ + 2n-1 --- Eq. 1
Multiplying Eq. 1 by 2 :-
2Tn = 2 + 22 + ........................ + 2n-1 + 2n --- Eq. 2
Subtracting Eq. 1 from Eq. 2 :-

Tn = 2n - 1

Using Induction to show that this method is the optimal :
For N=1
T1=21-1=1......( algo is optimal )
Assume algo is optimal for
N=1 , 2 , ....., K
For N = K + 1
Total moves = TK + 1 + TK
= 2K - 1 + 1 + 2K - 1
=2 * 2K - 1
=2K+1 - 1
=TK+1
Hence theTime Complexity of the Towers of Hanoi is 2n from the eqn.

Tn = 2n - 1