Notasi Asimtotik Menggunakan Big Oh,Big Omega,Big Teta

Kompleksitas Waktu

• Worst - case efficiency

           Tmax(n) = n

•  Best - case efficiency

           Tmin(n) = 1

• Average - case efficiency

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

Contoh pada Algoritma Isi Matriks

Procedure Isi_Matriks (input A,B : Matriks, output M,N : integer)

Deklarasi   i,j : integer
Algoritma
     input (M)
     input (N)
     for i ← 1 to M do
         for j ←1 to N do
           input (A[i,j])
          endfor

    endfor
    for i ← 1 to M do
         for j ←1 to N do
           input (B[i,j])
         endfor

   endfor
endprocedure

Tmin(n)  = n

Tmax(n) = 4n ≈ n

Tavg(n)  = n+n+n+4n/n

             =1/2n(4n)/n

             =1/2(4n)

             =2n ≈ n

1. Tmin(n) = n

Big O

T(n)   €   O (g(n))

T(n)   ≤  C. g(n²)

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

n  ≤ 1 (n²)

n=0  0 ≤ 0        jadi, C=1 , no=2

n=1  1 ≤ 1

n=2  2 ≤ 4 (√)

Ω (Big Omega)

T(n)   €   Ω (g(n))

T(n)   ≥  C. g(n²)

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

n  ≥ -1/2 (n²)

n=0  0 ≥ 0         jadi, C= - 1/2, no=1

n=1  1 ≥ -0,5  (√)

Θ (Big Theta)

C2g(n) ≤ t(n) ≤ C1g(n)

Batas Atas = n < t(n) = no = 2, C1 = 1
Batas Bawah = n > t(n)= no = 1, C2 = -1/2

Jadi  no = 1 ,C1 = 1 ,C2 = -1/2

2. Tmax(n) = 4n

Big O

T(n)   €   O (g(n))

T(n)   ≤  C. g(n²)

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

4n  ≤ 2 (n²)

n=0  0 ≤         jadi, C=2 , no=2

n=1  1 ≤ 2  (√)

Ω (Big Omega)

T(n)   €   Ω (g(n))

T(n)   ≥  C. g(n²)

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

4n  ≥ -1/2 (n²)

n=0  0 ≥ 0           jadi, C= - 1/2, no=1

n=1  4 ≥ -0,5  (√)

Θ (Big Theta)

C2g(n) ≤ t(n) ≤ C1g(n)

Batas Atas = n < t(n) = no = 2, C1 = 2
Batas Bawah = n > t(n)= no = 1, C2 = -1/2

Jadi  no = 1 ,C1 = 2 ,C2 = -1/2

3. Tavg(n) = 2n

Big O

T(n)   €   O (g(n))

T(n)   ≤  C. g(n²)

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

2n  ≤ 2 (n²)

n=0  0 ≤ 0      jadi, C=2 , no=2

n=1  2 ≤ 2  

n=2  4 ≤ 8  (√)

Ω (Big Omega)

T(n)   €   Ω (g(n))

T(n)   ≥  C. g(n²)

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

2n  ≥ -1/2 (n²)

n=0  0 ≥ 0         jadi, C= - 1/2, no=1

n=1  2 ≥ -0,5  (√)

Θ (Big Theta)

C2g(n) ≤ t(n) ≤ C1g(n)

Batas Atas = n < t(n) = no = 2, C1 = 2
Batas Bawah = n > t(n)= no = 1, C2 = -1/2

Jadi  no = 1 ,C1 = 2 ,C2 = -1/2

Contoh pada Algoritma Pangkat

Procedure Pangkat (input a,b : integer, output hasil : integer)
Deklarasi
   i : integer

Algoritma
     i ← 0
     hasil ← 1
     if (b=0) then
       hasil ← 1
     else
       for i ← 1 to b do
         hasil ← hasil * a

       endfor

    endif
endprocedure 

Tmin(n)  = n

Tmax(n) = 2n  ≈ n

Tavg(n)  = n+n+2n

             =1/2n(2n)

             =1/2(2n) ≈ n 

1. Tmin(n) = n

Big O

T(n)   €   O (g(n))

T(n)   ≤  C. g(n²)

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

n  ≤ 1 (n²)

n=0  0 ≤ 0        jadi, C=1 , no=2

n=1  1 ≤ 1

n=2  2 ≤ 4 (√)

Ω (Big Omega)

T(n)   €   Ω (g(n))

T(n)   ≥  C. g(n²)

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

 n  ≥ -1/2 (n²)

n=0  0 ≥ 0          jadi, C= - 1/2, no=1

n=1  1 ≥ -0,5  (√)

Θ (Big Theta)

C2g(n) ≤ t(n) ≤ C1g(n)

Batas Atas = n < t(n) = no = 2, C1 = 1
Batas Bawah = n > t(n)= no = 1, C2 = -1/2

Jadi  no = 1 ,C1 = 1 ,C2 = -1/2

2. Tmax(n) = 2n

Big O

T(n)   €   O (g(n))

T(n)   ≤  C. g(n²)

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

2n  ≤ 2 (n²)

n=0  0 ≤ 0      jadi, C=2 , no=2

n=1  2 ≤ 2  

n=2  4 ≤ 8  (√)

Ω (Big Omega)

T(n)   €   Ω (g(n))

T(n)   ≥  C. g(n²)

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

 2n  ≥ -1/2 (n²)

n=0  0 ≥ 0            jadi, C= - 1/2, no=1

n=1  2 ≥ -0,5  (√)

Θ (Big Theta)

C2g(n) ≤ t(n) ≤ C1g(n)

Batas Atas = n < t(n) = no = 2, C1 = 2
Batas Bawah = n > t(n)= no = 1, C2 = -1/2

Jadi  no = 1 ,C1 = 2 ,C2 = -1/2

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

Big O

T(n)   €   O (g(n))

T(n)   ≤  C. g(n²)

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

1/2(2n)  ≤ 2 (n²)

n=0  0 ≤ 0       jadi, C=2 , no=2

n=1  2 ≤ 2  

n=2  3 ≤ 8  (√)

Ω (Big Omega)

T(n)   €   Ω (g(n))

T(n)   ≥  C. g(n²)

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

1/2(2n)  ≥ -1/2 (n²)

n=0  0 ≥ 0             jadi, C= - 1/2, no=1

n=1  1 ≥ -0,5  (√)

Θ (Big Theta)

C2g(n) ≤ t(n) ≤ C1g(n)

Batas Atas = n < t(n) = no = 2, C1 = 2
Batas Bawah = n > t(n)= no = 1, C2 = -1/2

Jadi  no = 1 ,C1 = 2 ,C2 = -1/2 


Contoh 3

Procedure Nilai_Akhir (input Nilai:integer; output hasil:integer;)
Deklarasi
   nilai  :  integer
Algoritma
   Output('Masukkan Nilai Angka = ') Input(nilai)
   case nilai of
      'A': Output('sangan Baik')
      'B': Output('Baik')
      'C': Output('Kurang)
      'D': Output('Sangat kurang')
      'E': Output('Buruk Sekali')
   end
output(hasil)
Endprocedure

Tmin(n) = 1
Tmax(n) = n

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

1.Tmin(n) = 1

Big O
T(n)   €   O (g(n))
T(n)   ≤  C. g(n)
--------------------
1        ≤  O  (n)
1        ≤ ….  n
n = 0     1  ≤ 0 (x)                       JADI C = 2 ;  n = 1
n = 1     1  ≤ 1 (√)

Ω (Big Omega)
T(n)   €   Ω (g(n))
T(n)   ≥  C. g(n)
--------------------
1       ≥  Ω  (n)
1       ≥  … n
n = 0   1 ≥ 0 (√)                          JADI C = 1 ; n = 0
n = 1   1 ≥ 1 (√)

Θ (Big Theta)
C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas     = 1 < n = no = 1, C1 = 2
Batas Bawah = 1 > n = no = 0, C2 = 1
Jadi no= 1, C1= 2, C2 = 1

2.Tmax(n)=n

Big O
T(n)   €   O (g(n))
T(n)   ≤  C. g(n)
--------------------
N     ≤  O (n)
N     ≤ …. n
N = 0  0 ≤ 0 (√)                          JADI   C=1  ; N=0
N = 1  1 ≤ 1  (√)

Ω (Big Omega)
T(n)   €   Ω (g(n))
T(n)   ≥  C. g(n)
--------------------
n       ≥  Ω  (n)
n       ≥  … n
n = 0   0 ≥ 0 (√)                          JADI C=1 ; n=0
n = 1   1 ≥ 1 (√)

Θ (Big Theta)
C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas     = n < n = no = 0, C1 = 1
Batas Bawah = n > n = no = 0, C2 = 1
Jadi no= 0, C1= 1, C2 = 1

3.Tavg(n) = 1+2+n/n
                 = 1/2 n (1+(n))/n
                 = 1/2 (1+n)
                 = 1/2+n/2
Big O
T(n)   €   O (g(n))
T(n)   ≤  C. g(n)
--------------------
½+N/2      ≤  O (n)
½+N/2      ≤ …..n
N = 0  ½ ≤ 0 (x)                         JADI   C=2  ; N=1
N = 1  1  ≤ 1  (√)

Ω (Big Omega)
T(n)   €   Ω (g(n))
T(n)   ≥  C. g(n)
--------------------
½+N/2       ≥  Ω  (n)
½+N/2       ≥  … n
n = 0   ½  ≥ 0 (√)                        JADI  C = 1 ; n = 0
n = 1    1  ≥ 1 (√)

Θ (Big Theta)
C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas     = ½+N/2 < n = no = 1, C1 = 2
Batas Bawah = ½+N/2 > n= no = 0, C2 = 1

Jadi no= 1, C1= 2, C2 = 1


Contoh 4

procedure hitung(input a1,..,an:integer; input angka : integer; output hasil : integer)

deklarasi
  angka: integer

Algoritma
 input (angka)
  if (angka > 5) then
      output('Variabel "angka" lebih besar dari 5')
  else
      output('Variabel "angka" lebih kecil dari 5')
  endif
output(hasil)
endprocedure

Tmin = 1
Tmax = n
Tavg  = 1+2+n/n

1.Tmin(n) = 1

Big O
T(n)   €   O (g(n))
T(n)   ≤  C. g(n)
--------------------
1        ≤  O  (n)
1        ≤ ….  n
n = 0     1  ≤ 0 (x)                       JADI C = 2 ;  n = 1

Ω (Big Omega)
T(n)   €   Ω (g(n))
T(n)   ≥  C. g(n)
--------------------
1       ≥  Ω  (n)
1       ≥  … n
n = 0   1 ≥ 0 (√)                          JADI C = 1 ; n = 0
n = 1   1 ≥ 1 (√)

Θ (Big Theta)
C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas    = 1 < n = no = 1, C1 = 2
Batas Bawah = 1 > n = no = 0, C2 = 1
Jadi no = 1, C1= 2, C2 = 1

2.Tmax(n) = n

Big O
T(n)   €   Ω (g(n))
T(n)  ≤    C. g(n)
--------------------
n       ≤   Ω  (n)
n       ≤   … n
n=0   0 ≤  0 (√)                           JADI C = 1 ; n = 0
n=1    1 ≤  1 (√)

Ω (Big Omega)
T(n)   €   Ω (g(n))
T(n)   ≥  C. g(n)
--------------------
n       ≥  Ω  (n)
n       ≥  … n
n = 0   0 ≥ 0 (√)                          JADI C = 1 ; n = 0
n = 1   1 ≥ 1 (√)

Θ (Big Theta)
C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas = n < n = no = 0, C1 = 1
Batas Bawah = n > n= no = 0, C2 = 1
Jadi no= 0, C1= 1, C2 = 1

3.Tavg(n) = 1+2+n/n
                 = 1/2 n (1+(n))/n
                 = 1/2 (1+n)
                 = 1/2+n/2            
Big O
T(n)   €   O (g(n))
T(n)   ≤  C. g(n)
--------------------
½+N/2      ≤  O (n)
½+N/2      ≤ …..n
N = 0  ½ ≤ 0 (x)                         JADI C = 2 ; N = 1
N = 1   1 ≤ 1 (√)

Ω (Big Omega)
T(n)   €   Ω (g(n))
T(n)   ≥  C. g(n)
--------------------
½+N/2       ≥  Ω  (n)
½+N/2       ≥  … n
n = 0   ½  ≥ 0 (√)                        JADI C = 1 ; n = 0
n = 1    1  ≥ 1 (√)

Θ (Big Theta)
C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas     = ½+N/2 < n = no = 1, C1 = 2
Batas Bawah = ½+N/2 > n = no = 0, C2 = 1
Jadi no = 1, C1= 2, C2 = 1


Contoh 5

Procedure GanjilGenap ((input a1,..,an:integer;input angka:integer; output hasil:integer)
deklarasi
  angka:integer
Algoritma
  output('Masukkan sebuah angka: ')
  input(angka)
  if (angka mod 2 = 0) then
      output('Angka yang anda masukkan merupakan bilangan genap')
  else
      output('Angka yang anda masukkan merupakan bilangan ganjil')
  endif
  output(hasil)
endprocedure

Tmin(n) = 1
Tmax(n) = n
Tavg(n) = 1+2+n/n

Tmin(n) = 1

Big O
T(n)   €   O (g(n))
T(n)   ≤  C. g(n)
--------------------
1        ≤  O  (n)
1        ≤ ….  n
n = 0   1  ≤ 0 (x)                       JADI : C = 2 ;  n = 1
n = 1   1  ≤ 1 (√)


Ω (Big Omega)
T(n)   €   Ω (g(n))
T(n)   ≥  C. g(n)
--------------------
1       ≥  Ω  (n)
1       ≥  … n
n = 0   1 ≥ 0 (√)                        JADI : C = 1 ; n = 0
n = 1   1 ≥ 1 (√)


Θ (Big Theta)
C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas     = 1 < n = no = 1, C1 = 2
Batas Bawah = 1 > n = no = 0, C2 = 1
Jadi no = 1, C1 = 2, C2 = 1

Tmax(n) = n

Big O
T(n)   €   O (g(n))
T(n)   ≤  C. g(n)
--------------------
N     ≤  O (n)
N     ≤  ... n
N = 0   0 ≤ 0 (√)                       JADI :  C:1  ; N=0
N = 1   1 ≤ 1 (√)

Ω (Big Omega)
T(n)   €   Ω (g(n))
T(n)   ≥  C. g(n)
--------------------
n       ≥  Ω  (n)
n       ≥  … n
n = 0   0 ≥ 0 (√)                        JADI : C:1 ; n:0
n = 1   1 ≥ 1 (√)

Θ (Big Theta)
C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas     = n < n = no = 0, C1 = 1
Batas Bawah = n > n = no = 0, C2 = 1
Jadi no = 0, C1 = 1, C2 = 1

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

Big O
T(n)   €   O (g(n))
T(n)   ≤  C. g(n)
--------------------
½+N/2      ≤  O (n)
½+N/2      ≤ …..n
N = 0  ½  ≤ 0 (x)                      JADI :  C:2  ; N=1
N = 1   1  ≤ 1  (√)

Ω (Big Omega)
T(n)   €   Ω (g(n))
T(n)   ≥  C. g(n)
--------------------
½+N/2       ≥  Ω  (n)
½+N/2       ≥  … n
n = 0   ½  ≥ 0 (√)                      JADI : C:1 ; n:0
n = 1    1  ≥ 1 (√)

Θ (Big Theta)
C2g(n) ≤ t(n) ≤ C1g(n)
Batas Atas     = ½+N/2 < n = no = 1, C1 = 2
Batas Bawah = ½+N/2 > n = no = 0, C2 = 1
Jadi no = 1, C1 = 2, C2 = 1