Analisis Algoritma Rekursif

Algoritma Rekursif

function Faktorial (input n : integer) → integer
{menghasilkan nilai n!, n tidak negatif}s waktu

Algoritma :

 if n=0 then

   return 1

else

    return ( n*faktorial (n-1))

 endif;


Kompreksitas waktu :

T(n) = 1+T(n-1)
T(n) = 1+1+T(n-2)=2+T(n-2)
T(n) = 2+1+T(n-3)=3+T(n-3)
     = ...
     = ...
     = n+T(0)
     = n+0
T(n) =n
T(n) =T(n)ϵO(n)