Menghitung Big oh (O), Omega (Ω) dan Theta(θ) (1)

Menentukan big oh , omega dan tetha pada algoritma menentukan sks lebih, berikut adalah algoritmanya :

 Procedure Menentukan_SKS_Lebih(input A1...An: real)

Deklarasi:

         i : integer

Algoritma :

         input(n)

         for i =1 to n do

            if (IP ≥ 3.25) then

               SKS ← SKS +5

               output ('Anda bisa Menambah 5 SKS lebih untuk semester Selanjutnya')

            else

            if (IP ≥ 3.00) and (IP <3.25) then

               SKS ← SKS +2              

               output ('Anda bisa Menambah 2 SKS lebih untuk semester Selanjutnya')

            else

            if (IP < 3.00) then

               SKS ← SKS +0

               output('Anda Tidak bisa Menambah SKS lebih untuk semester Selanjutnya')

            endif

            endif

            endif

endprocedure

Langkah pertama cari cari t min (n), t max(n) dan t avg(n)nya berkit hasilnya

T min(n)= n

T max(n)=3n

T avg(n)=n+3n
                  2

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

t min(n)=n

-Big oh(O)

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

n≤2n

n₀ =0

c =2

-Big omega(Ω)

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

n ≥ 1/2n

n₀ =0

c =1/2

-big theta(θ)

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

batas atas 

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

1/2n≤n

n₀ =0

c1 =1/2

batas bawah

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

n≤2n

 n₀ =0

c2 =2

untuk t max

t max(n)=3n

-Big oh(O)

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

3n≤3n+1

n₀ =0

c =3

-Big omega(Ω)

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

3n ≥ n +3

n₀ =2

c =1

-big theta(θ)

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

batas atas 

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

n + 3 ≤3n

n₀ =2

c1 =1

batas bawah

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

n≤2n

 n₀ =0

c2 =2

untuk t average

T avg(n)=n+3n = 2n
                  2

t(n)=2n

-Big oh(O)

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

2n≤2n+1

n₀ =0

c =2

-Big omega(Ω)

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

2n ≥ n + 2

n₀ =2

c =1

-big theta(θ)

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

batas atas 

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

n + 2 ≤2n

n₀ =2

c1 =1

batas bawah

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

2n≤2n + 1

 n₀ =0

c2 =2