Analisis Matematis Algoritma Rekursif Fungsi Fibonacci

function fibonacci(Input n:integer)→integer

Kamus

Algoritma

  If (n=0)

    Then

       fibonacci ← 1

    Else

       If (n=1)

         Then

                fibonacci ← 1

         Else

                Fibonacci ← (fibonacci(n-1) + fibonacci(n-2))

      Endif

   Endif

Endfunction

Operasi Dasar Utama : Penjumlahan

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

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

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

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

T(n) = ...

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

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

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

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

Jadi, T(n) =  n + (n-(n-2))