Analisis Algoritma Rekursif - Pangkat

Algoritma Rekursif Pangkat

function Pangkat(x, y : integer) → integer
Deklarasi lokal :
{tidak ada}
Algoritma :
        if y=0 then
           return 1
        else
          return (x*Pangkat(x,y-1))
        endif.

operasi dasar utama : perkalian (*) (1 kali)

T(n) = 0                  , n = 0
T(n) = T(n - 1) + 1 , n > 0

T(n) = T (n - 1) + 1
        = T (n - 1 - 1) + 1 = T(n - 2) + 1
        = T (n - 2 -1) + 1 = T(n - 3) + 1
            |
            |
            |
T(n) = (n - i) + i
T(n) = (n - n) + n
T(n) = n
T(n) = n ϵ  O (n)