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

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

 

Procedure banyak_suku

Deklarasi

  s  : real

 x,y,n :integer

Algoritma

 Input(n)

 s ← -1/3

 x ← 1

 y ← 3

 for i ← 2 to N do

     X ← X * i

     y ← Y + i

    if (i mod 2 = 1) then

       S ← s - X/y

    else

       S ← s + X/Y

    endif

 endfor

    output('S = ')

 endprocedure

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

T min(n)=3+4=7

T max(n)=n+3

T avg(n)=3+n
                  n

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

t min(n)=n

-Big oh(O)

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

7≤1(1)

7≤2(2)

7≤3(3)

c=3
n0=n

-Big omega(Ω)

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

7 ≥ 1(1)
7 ≥2(2)

n₀ =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))

7≤1(1)

7≤2(2)

7≤3(3)

n₀ =n

c =3

-Big omega(Ω)

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

7 ≥ 1(1)

7 ≥ 2(2)

 

n₀ =n

c =2

-big theta(θ)

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

batas atas 

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

2n ≤ 7 ≤3n

n₀ =n

c1 =3

batas bawah

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

2n≤7≤3n

 n₀ =n

c2 =3

untuk t average

T avg(n)=3+n
                  n

t(n)=2n

-Big oh(O)

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

7≤1(1)

7≤2(2)

7≤3(3) 

n₀ =n

c =3

-Big omega(Ω)

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

  7≥ 1(1)

7≥ 2(2)

n₀ =2

c =2

-big theta(θ)

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

batas atas 

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

2n ≤ 7 ≤3n

n₀ =n

c1 =3

batas bawah

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

2n ≤ 7 ≤3n

 n₀ =n

c2 =3