Perbaikan Rekursif (2)

Menganalisis algoritma Menghitung c x d dengan c dan d bilangan bulat positif.

Berikut adalah algoritmanya :

Function perkalian(input c,d: integer)→integer

Kamus:

Algoritma:

If d = 1 then

    
   c ← c

else

   
   c ← c + perkalian(c,d-1)

endif

endfunction

penyelesaian :

      

      1.      Operasi dasar utama = penjumlahan

      

      2.      Menentukan hubungan recurrence

Basis :

Mengembalikan ke nilai c awal, jika d = 1;

recurrence :

c =  c + c * (d-1),  jika n > 1;

Tambah(+)

Penjumlahan(+)=1

F(x-1)+1

T(n-1)+1

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

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

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

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

T(n-3)= T(n-4)+1

Titik henti T(1)=0

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

        = T(n-2)+1+1

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

T(n)= T(n-i)+i

n-i=1

-i=1-n

I=n-1

T(n)= T(n-i)+i

T(n-(n-1)+(n-1)

T(n-n+1)+(n-1)

T(1)+(n-1)

0+(n-1)

n-1 £ O(n)