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
Prof. Ashay Dharwadker