Analisis Algoritma Rekursif

Algoritma Rekursif

function FIBO(input N : integer) → integer

{mengirimkan bilangan fibbonacci dengan cara rekursif}

Algoritma:

int fibo(int n)

   if(n==0)

     return 0;

   else if(n==1)

     return 1;

   else

     //fungsi rekursif

     return fibo(n-1)+fibo(n-2);

Kompleksitas Waktu :

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

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

         =.....

         =.....

         =.....

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

T(n) = O(3n )