menghitung notasi asimtotik

Procedure faktorial (input  N : integer,output  Fak :  real)

{I.S. : harga N sudah terdefinisi}

{F.S. : menghasilkan harga faktorial dari N}

Kamus:

     I : integer {pencacah}

Algoritma:

     If  (N=0) or (N=1)

          Then

                Fak  ←   1

           Else

                Fak  ←   1

                For i ← 2 to N do

                     Fak ← Fak * i

                Endfor

     Endif

endprocedure

----- -----------------------------------------------------------

Tmin(n)    = 1

Tmax(n)    = 3n

Tavg(n)    = (1+3n)/2

= 4/2n

= 2n

Kemudian meghitung notasi  big oh, omega dan theta nya tiap T(n)

t min(n)=n

-Big oh(O)

T(n)≤O (g(n))

1≤1(1)

1≤2(2)

1≤3(3)

c=3

n0=n

-Big omega(Ω)

T(n)≥ Ω (g(n))

1 ≥ 1(1)

1 ≥2(2)

n0 =n

c =2

-big theta(θ)

 C2(g(n)) ≤ T(n) ≥ C1 (g(n))

batas atas

untuk t max

t max(n)=3n

-Big oh(O)

T(n)≤O (g(n))

3n≤1(1)

3n≤2(2)

3n≤3(3)

n0 =n

c =3

-Big omega(Ω)

T(n)≥ Ω (g(n))

3n ≥ 1(1)

3n ≥ 2(2)

n0 =n

c =2

-big theta(θ)

 C1(g(n)) ≤ T(n) ≤ C2 (g(n))

batas atas

     C1(g(n)) ≤ T(n)

2n ≤ 1 ≤3n

n0 =n

c1 =3

batas bawah

     T(n) ≤ C2 (g(n))

2n≤1≤3n

     n0 =n

c2 =3

untuk t average

T avg(n)=3+n/n

t(n)=2n

-Big oh(O)

T(n)≤O (g(n))

1≤1(1)

1≤2(2)

1≤3(3)

n0 =n

c =3

-Big omega(Ω)

T(n)≥ Ω (g(n))

1≥ 1(1)

1≥ 2(2)

n0 =2

c =2

-big theta(θ)

 C2(g(n)) ≤ T(n) ≤ C1 (g(n))

batas atas

C2(g(n)) ≤ T(n)

2n ≤ 1 ≤3n

n0 =n

c1 =3

batas bawah

T(n) ≤ C1 (g(n))

2n ≤ 1 ≤3n

 n0 =n

c2 =3