Analisis Matematis Algoritma 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;

     

      3.      penyelesaian recurrence: