Desain Analisis Algoritma
1. Analisis Algoritma Fibonacci
Input := n
Fibonacci := 0
If n = 0 or n = 1
Then Fibonacci := n
Else
Then Fibonacci := Fibonacci (n-1) + Fibonacci (n-2)
End if

Estimasi waktu algoritma fibonacci :

a. Menentukan matrix untuk ukuran input : n , karena n mempengaruhi jumlah pemanggilan fungsi rekursif

b. Basic operation : n = 0 and n = 1

c. Case : tidak terdapat best case , average case , maupun worst case karena untuk n tertentu banyaknya pemanggilan fungsi rekursif selalu sama

d. Persamaan rekursif banyaknya eksekusi basic operation :
Hubungan C(n) dengan C(n-1) adalah :
C(n) = C(n – 1) + 1 untuk n > 1 (recursive case)
C(1) = 1, base case

C(n-1) = C(1)
C(n) = C(n-1) + C (n-2) + C(1)
Alternatif, kita dapat menggunakan pohon rekursif dengan kedalaman n dan secara intuitif fungsi asimtotik ini adalah O(2n) . Kita dapat membuktikan estimasi ini dengan cara induksi
Base n=1
Asumsikan C(n-1) = O(2n-1) , kemudian
C(n) = C(n-1) + C(n-2) + C(1) , adalah sama dengan
C(n) = O(2n-1) + O(2n-2) + C(1) = O(2n)
Dan T(n) = Cop x C(n)
= 1 x 2n