Menghitung Kompleksitas Waktu dari Algoritma Rekursif

1. Fibonachi

Algoritma
  input(n)
  awal ← 0
  akhir ← 1

   for i=1 to n do
     output(akhir)
     fibo ← awal + akhir
     awal ← akhir
     akhir ← fibo

Kompleksitas Waktu

untuk basis, tidak ada perulangan yaitu T(1) = 1 (kondisi awal), n = 1
                    perulangan yaitu T(1) = 1 ; n>1
untuk rekurens, T(3n + 2)

Menghitung T(n)
T(n) = 1 + T(3n + 2)
T(3n+2) = 1 + T(3(3n+2) + 2) = 1 + T(9n + 8) = T(9n + 9)
T(9n+9) = 1 + T(3(9n+9) + 2) = 1 + T(27n + 29) = T(27n + 30)
        = .....
        = .....
        = n + T(3n + 2)
        = n + n = 2n

jadi T(n) = 2n
T(n) € O(n)

2. rata-rata

Algoritma
    input(data)
    i = 1
    jumlah = 0 

    while i <= data do
        scanf(nilai)
        i ← i+1
        jumlah ← jumlah + nilai
    endwhile

    hasil ← jumlah / data
    output(hasil)

Kompleksitas Waktu
untuk basis, tidak ada perulangan yaitu T(0) = 0 (kondisi awal), n = 0
                    perulangan yaitu T(1) = 1 ; n>=1
untuk rekurens, T(2n + 1)

Menghitung T(n)
T(n) = 1 + T(2n + 1)
T(n) = 1 + 1 + T(2n + 1) = 2 + T(2n + 1)
T(n) = 2 + 1 + T(2n + 1) = 3 + T(2n + 1)
        = .....
        = .....
        = n + T(n)
        = n + n = 2n

jadi T(n) = 2n
T(n) € O(n)

3.tukar coklat
Algoritma
  input(jumlah)
  coklat ← 0;

  while (jumlah>=3) and (jumlah<= 100) do
    tukar ← jumlah div 3
    coklat ← coklat + tukar
    sisa ← jumlah mod 3
    jumlah ← tukar + sisa
  endwhile

  output(coklat)

Kompleksitas Waktu
untuk basis, tidak ada perulangan yaitu T(0) = 0 (kondisi awal), n = 0
                    perulangan yaitu T(1) = 1 ; n>=1
untuk rekurens, T(4n + 1)

Menghitung T(n)
T(n) = 1 + T(4n + 1)
T(n) = 1 + 1 + T(4n + 1) = 2 + T(4n + 1)
T(n) = 2 + 1 + T(4n + 1) = 3 + T(4n + 1)
        = .....
        = .....
        = n + T(n)
        = n + n = 2n

jadi T(n) = 2n
T(n) € O(n)