Menghitung T(n) Pseudocode Rekursif

Program Tower Hanoi

Procedure Hanoi (Input N,A,B,C : integer)

{I.S. : }

{F.S. : }

Kamus :

Algoritma :

If N = 1

  then

  Output (‘Pindahkan Piringan dari ‘,A,’Ke’,B)

Else Hanoi (n-1,A,C,B)

Output(‘Pindahkan Piringan dari ‘,A,’Ke’,B)

Hanoi(n-1, C,B,A)

Endif

Mencari T(n)

 

Operasi Dasar(=)

Kompleksitas Waktu

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

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

        = 1 + 2 + 2² (1+2T(n-3)) = 1+2+2²+2³T(n-3)

       =   .................

       =   .................

       = (1+2+2²+....+2ⁿ⁻²)+2ⁿ⁻¹T(1)

      = 1+2+2²+.....+2ⁿ⁻¹

      = 2ⁿ⁻¹

Jadi

T(n) = 2ⁿ⁻¹

T(n) € О(2ⁿ)

Relasi rekurrens

                1                        ,n=1

T(n)        2T(n-1)+1            ,n>1