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

program Menampilkan_bintang

Deklarasi :

i,j,n : integer

Algoritma :

  input(n);

  for i ← n downto 1 do

      for j ← n downto 1  do

           if j ≤ i then

                 output('*')

           else

                 output(' ');

           endif

     endfor 

 endfor

end.

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

T min(n)=n²

T max(n)=2n²

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

                  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²≤n² +1

n₀ =0

c =1

-Big omega(Ω)

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

n² ≥n² -1

n₀ =0

c =1

-big theta(θ)

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

batas atas 

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

n² -1≤ n² 

n₀ =0

c1 =1

batas bawah

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

n² ≤ n² +1

 n₀ =0

c2 =1

untuk t max

t max(n)=2n²

-Big oh(O)

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

2n²≤2n² +1

n₀ =0

c =2

-Big omega(Ω)

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

2n² ≥2n² -1

n₀ =0

c =2

-big theta(θ)

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

batas atas 

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

2n² - 1 ≤2n²

n₀ =0

c1 =2

batas bawah

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

2n²≤2n² + 1

 n₀ =0

c2 =2

untuk t average

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

t(n)=3/2n²

-Big oh(O)

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

3/2n²≤n²

n₀ =0

c =2

-Big omega(Ω)

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

3/2n² ≥-n²

n₀ =0

c =-1

-big theta(θ)

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

batas atas 

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

-n²≤3/2n²

n₀ =0

c1 =-1

batas bawah

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

3/2n²≤n²

 n₀ =0

c2 =1