Notasi Asimtotik - Menghitung Big OH, Big Omega, dan Big Theta

Contoh 1 : Algoritma Program Biaya Sewa

program Biaya_Sewa

Deklarasi

  biaya : integer

  jenis,tipe : char

Algoritma

  input (jenis)

  if (jenis='A') then

     input (tipe)

     case tipe of

        'A' : biaya <- 300000

        'B' : biaya <- 100000

        'C' : biaya <- 65000

     else

          output('Tipe Mobil yang anda pilih tidak ada')

     endcase

  endif

  else if (jenis='B') then

      Input(kelas)

      case kelas of

         'A' : biaya <- 150000

         'B' : biaya <- 50000

         'C' : biaya <- 32500

      else

          Output('Tipe Sepeda Motor yang anda masukkan tidak ada');

     endcase

  endelseif

  else

      output('Jenis Kendaraan yang anda pilih tidak ada');

  endelse

  Output (biaya)

end.

  

Operasi Dasar	Tmax(n)	Tmin(n)	Tavg(n)
<-	n	0	1/2n
=	n	0	1/2n
input	n+1	n	1/2n + 1/2
output	n+1	n	1/2n + 1/2

Operasi dasar yang paling penting adalah (output)

Tmax(n) = n + n + (n+1) + (n+1)

                Tn = n+1 = n

-Big-oh(O)

Tn =  ≤ Cg(n)

n+1≤ 5(n)

1+1 ≤ 5(1)        ;n=1

2 ≤ 5                 ;C=5

T_max­_­(n)= n+1 = O (n) untuk n ≥ 1 dan C ≥ 5

Jadi Tn= n+1 termasuk kedalam himpunan Big-oh(O)

-Big -Omega (Ω)

Tn =  ≥ Cg(n)

n+1 ≥ 1(n)

1+1 ≥ 1(1)             ;n=1

2 ≥ 1                      ;C=1

T_max­_­(n)= n+1= Ω(n) untuk n ≤ 2 dan C  ≤ 1

Jadi Tn= n+1 tidak termasuk ke dalam himpunan -Big -Omega (Ω)

-Big -Teta Θ

Karena T_max­_­(n)= n+1=O(n) dan T_max­_­(n)= n+1= Ω(n) maka T_max­_­(n)= n+1= Θ(n)

Tmin(n) = 0 + 0 + (n) + (n)

                Tn = n

-Big-oh(O)

Tn =  ≤ Cg(n)

n ≤ 2(n)

1 ≤ 2(1)        ;n=1

1 ≤ 2             ;C=2

T_min­_­(n)= n = O (n) untuk n ≥ 1 dan C ≥ 2

Jadi Tn= n termasuk kedalam himpunan Big-oh(O)

-Big -Omega (Ω)

Tn =  ≥ Cg(n)

n ≥ 1/2(n)

1 ≥ 1/2(1)             ;n=1

1 ≥  1/2                 ;C=1/2

T_min­_­(n)= n= Ω(n) untuk n ≤ 1 dan C  ≤ 1/2

Jadi Tn= n tidak termasuk ke dalam himpunan -Big -Omega (Ω)

-Big -Teta Θ

Karena T_min­_­(n)= n=O(n) dan T_min­_­(n)= n= Ω(n) maka T_min­_­(n)= n= Θ(n)

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

                Tn = 1/2n = n

-Big-oh(O)

Tn =  ≤ Cg(1/2n)

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

1/2.1 ≤ 2(1/2.1)        ;n=1

1/2 ≤ 1                      ;C=2

T_avg­_­(n)= 1/2n = O (n) untuk n ≥ 1 dan C ≥ 2

Jadi Tn= 1/2n termasuk kedalam himpunan Big-oh(O)

-Big -Omega (Ω)

Tn =  ≥ Cg(n^2)

17n ≥ 8(n^2)

17+5 ≥ 8(5^2)              ;n=5

22 ≥ 200                      ;C=8

T_avg­_­(n)= 17n= Ω(n) untuk n ≤ 5 dan C  ≤ 8

Jadi Tn= 17n tidak termasuk ke dalam himpunan -Big -Omega (Ω)

-Big -Teta Θ

Karena T_avg­_­(n)= 1/2n=O(n) dan T_avg­_­(n)= 1/2n= Ω(n) maka T_avg­_­(n)= 1/2n= Θ(n)

Contoh 2 : Algoritma Procedure Selection Sort

Data yang harus di urut kan dengan metode selection yaitu :

3

1

4

5

2

procedure sort_selection(var data:larik)

Deklarasi

i,j,result:integer

 n<--5;

 for i <-- 1 to n do

 for j <-- i to n do

  if data[j] < data [i] then

  result <-- data [j]

  data [j] <-- data [i]

  data [i] <-- result;

endfor

endfor

endfor

Operasi Dasar	Tmax(n)	Tmin(n)	Tavg(n)
<--	n+23	n+11	17n
<	n+5	n+5	0

Operasi dasar yang paling penting adalah (<--)

Tmax(n) = n+23 + n+5

 Tn = n+23 = n

-Big-oh(O)

Tn =  ≤ Cg(n^2)

n+23 ≤ 25(n^2)

10+23 ≤ 25(10^2)        ;n=10

33 ≤ 2500                    ;C=25

T_max­_­(n)= n+23 = O (n) untuk n ≥ 10 dan C ≥ 25

Jadi Tn= n+23 termasuk kedalam himpunan Big-oh(O)

-Big -Omega (Ω)

Tn =  ≥ Cg(n^2)

n+23 ≥ 8(n^2)

5+23 ≥ 8(5^2)             ;n=5

28 ≥ 200                      ;C=8

T_max­_­(n)= n+23= Ω(n) untuk n ≤ 5 dan C  ≤ 8

Jadi Tn= n+23 tidak termasuk ke dalam himpunan -Big -Omega (Ω)

-Big -Teta Θ

Karena T_max­_­(n)= n+23=O(n) dan T_max­_­(n)= n+23= Ω(n) maka T_max­_­(n)= n+23= Θ(n)

Tmin(n) = n+11 + n+5

               Tn = n+11 = n

-Big-oh(O)

Tn =  ≤ Cg(n^2)

n+11 ≤ 25(n^2)

10+11 ≤ 25(10^2)        ;n=10

21 ≤ 2500                    ;C=25

T_min­_­(n)= n+11 = O (n) untuk n ≥ 10 dan C ≥ 25

Jadi Tn= n+11 termasuk kedalam himpunan Big-oh(O)

-Big -Omega (Ω)

Tn =  ≥ Cg(n^2)

n+11 ≥ 8(n^2)

5+11 ≥ 8(5^2)              ;n=5

16 ≥ 200                      ;C=8

T_min­_­(n)= n+11= Ω(n) untuk n ≤ 5 dan C  ≤ 8

Jadi Tn= n+11 tidak termasuk ke dalam himpunan -Big -Omega (Ω)

-Big -Teta Θ

Karena T_min­_­(n)= n+11=O(n) dan T_min­_­(n)= n+11= Ω(n) maka T_min­_­(n)= n+11= Θ(n)

Tavg(n) = (23-11)/2 n + (5-5)/2 n
                    =    17n + 0

               Tn = 17n = n

-Big-oh(O)

Tn =  ≤ Cg(n^2)

17n ≤ 25(n^2)

17+10 ≤ 25(10^2)        ;n=10

27 ≤ 2500                    ;C=25

T_avg­_­(n)= 17n = O (n) untuk n ≥ 10 dan C ≥ 25

Jadi Tn= 17n termasuk kedalam himpunan Big-oh(O)

-Big -Omega (Ω)

Tn =  ≥ Cg(n^2)

17n ≥ 8(n^2)

17+5 ≥ 8(5^2)              ;n=5

22 ≥ 200                      ;C=8

T_avg­_­(n)= 17n= Ω(n) untuk n ≤ 5 dan C  ≤ 8

Jadi Tn= 17n tidak termasuk ke dalam himpunan -Big -Omega (Ω)

-Big -Teta Θ

Karena T_avg­_­(n)= 17n=O(n) dan T_avg­_­(n)= 17n= Ω(n) maka T_avg­_­(n)= 17n= Θ(n)

Contoh 3 : Algoritma mencari x di dalam elemen menggunakan metode sequential search

Procedure Pencarian Berurutan (input: a1,a2,a3…,a(n) : integer, x :integer,

{

mencari nilai x di dalam elemen a1,a2,a3…a(n). lokasi (indeks elemen) tempat x ditemukan diisi ke daalam idx. Jika x tidak ditemukan, maka idx diisi dengan 0.

            Masukan : a1,a2,a3…a(n)

            Keluaran : idx

}

Algoritma

i ← 1

ketemu ← false

while ( 1 ≤ n) and (not ketemu) do

            if a(i) = x then

                        ketemu ← true

            else

                        i ← i + 1

            endif

            endwhile  { i > n or ketemu }

            if  ketemu then {x ditemukan}

                        idx ← i

            else

                        idx ← 0 {x tidak ditemukan}

            endif

Operasi Dasar	Tmax(n)	Tmin(n)	Tavg(n)
←	n+2	n+3	1/2n
=	n	n	0
≤	n+1	1	1/2(n+1)
and	n+1	1	1/2(n+1)
+	n	0	1/2n

Operasi dasar yang paling penting adalah (←)

Penyelasaian:

            Algoritma pencarian membandingkan setiap elemen larik dengan x, mulai dari elemen pertama sampai x ditemukan atau sampai elemen terakhir. Jika x ditemukan, maka proses pencarian dihentikan. Kita akan menghitung jumlah operasi perbandingan elemen larik yang terjadi selama pencarian ( a (i) = x ). Operasi perbandingan yang lain, seperti i ≤ n tidak akan dihitung. Operasi perbandingan elemen-elemen larik adalah abstrak yang mendasari algoritma-algoritma pencarian.

1. Kasus terbaik Tmin : ini terjadi bila a (i) = x

Operasi perbandingan elemen ( a (i) = x) hanya dilakukan satu kali, 

maka Tmin (n) = (n+3) + n + 1 + 1 + 0
         Tn = n+3 = n

2. Kasus terburuk Tmax: bila a(n) = x atau x tidak ditemukan.

Seluruh elemen larik dibandingkan, jumlah perbandingan elemen larik (a (i) = x) 

maka Tmax(n) = (n+3) + n + (n+1) + (n+1) + n
         Tn = n+3 = n

.

3. Kasus rata-rata Tavg : Jika ditentukan pada posisi ke-j, maka operasi perbandingan ( a(i) = x)

Dilakukan sebanyak j kali. Jadi, kebutuhan waktu rata-rata algoritma adalah:

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

maka Tavg(n) = 1/2n + 0 + 1/2(n+1) + 1/2(n+1) + 1/2n
         T(n) = 1/2n = n

 

Tmax: Tn = n+3 = n

Big O

n+3 ≤ Cg (n²)

n+3 ≤ 10 (n²)

n=0 0+3 ≤ 0

n=1 1+3 ≤ 10

n=2 2+3 ≤ 40

n=10 10+3 ≤ 1000

n=100 100+3 ≤ 100000

C=10 Tn = n+3

Big Omega

n+3 ≥ Cg (n²)

n+3 ≥ 10 (n²)

n=0 0+3 ≥ 0

n=1 1+3 ≥ 10

n=2 2+3 ≥ 40

n=10 10+3 ≥ 1000

n=100 100+3 ≥ 100000

C=10 Tn = n+3

Big Teta

Karena Tmax­_­(n)= n+3=O(n) dan Tmax_­(n)= n+3= Ω(n) maka Tmax­_­(n)= n+3= Θ(n)

Tmin: Tn = n+2 = n

Big Oh

n+2 ≤ Cg (n²)

n+2 ≤ 10 (n²)

n=0 0+2 ≤ 0

n=1 1+2 ≤ 10

n=2 2+2 ≤ 40

n=10 10+2 ≤ 1000

n=100 100+2 ≤ 100000

C=10 Tn = n+2

Big Omega:

n+2 ≥ Cg (n²)

n+2 ≥ 10 (n²)

n=0 0+2 ≥ 0

n=1 1+2 ≥ 10

n=2 2+2 ≥ 40

n=10 10+2 ≥ 1000

n=100 100+2 ≥ 100000

C=10 Tn = n+2

Big Teta

Karena Tmin­_­(n)= n+2=O(n) dan Tmin(n)= n+2= Ω(n) maka Tmin(n)= n+2= Θ(n)

Tavg: Tn = 1/2n = n

Big O

1/2n ≤ Cg (n²)

1/2n ≤ 10 (n²)

n=0 1/2 x 0 ≤ 0

n=1 1/2 x 1 ≤ 10

n=2 1/2 x 2 ≤ 40

n=10 1/2 x 10 ≤ 1000

n=100 1/2 x 100 ≤ 100000

C=10 Tn = 1/2n

Big Omega

1/2n ≥ Cg (n²)

1/2n ≥ 10 (n²)

n=0 1/2 x 0 ≥ 0

n=1 1/2 x 1 ≥ 10

n=2 1/2 x 2 ≥ 40

n=10 1/2 x 10 ≥ 1000

n=100 1/2 x 100 ≥ 100000

C=10 Tn = 1/2n

Big Teta

Karena Tavg­_­(n)= 1/2n=O(n) dan Tavg(n)= 1/2n= Ω(n) maka Tavg(n)= 1/2n= Θ(n)

Contoh 4 : Algoritma Cetak Nama Lengkap

program ctkNamaLengkap

Deklarasi
nama : array [1..10] of string[15]

nmLkp, nm: string [150]

n, i : integer

Algoritma

   input(n)

   nmLkp <- ' '

   for i <- 1 to n do

      output("Masukkan nama ke ",i," : ")

      input(nama[i])

      nmLkp <- nmLkp + nama[i] + ' '

   endfor

   if nmLkp = 3

        nm <- "Nama anda sudah pas"

   else if nmLkp > 3

        nm <- "Nama anda terlalu panjang"

   else

        nm <- "Nama anda terlalu singkat"

   endif

   output("Nama lengkap anda adalah",nmLkp)

   output(nama)

Operasi Dasar	Tmax(n)	Tmin(n)	Tavg(n)
<-	5n+1	2n+1	1/2(5n+1 - 2n+1)
=	n	n	1/2n
input	n+1	n	1/2n + 1/2
output	n+1	n	1/2n + 1/2

Operasi dasar yang paling penting adalah (<-)

Tmax(n) = (5n+1) + n + (n+1) + (n+1)

                Tn = 5n+1 = n

Tmin(n) = (2n+1) + n + n + n

                Tn = 2n = n

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

                (1 1/2n+1) + 1/2n + (1/2n + 1/2) + (1/2n + 1/2)

                Tn = 1 1/2n + 1 = n

Notasi Asimtotik

Big Oh (O)

Tmax(n) = 5n+1

5n + 1 ≤ Cg (n²)

5n + 1 ≤ 6 (n²)

n = 0      5(0) + 1 ≤ 0

n = 1      5(1) + 1 ≤ 6

n = 5      5(5) + 1 ≤ 6(25)

n = 10    5(10) + 1 ≤ 6(100)

c ≥ 7      n ≥ 1

Tmin(n) = 2n

2n + 1 ≤ Cg (n)

2n + 1 ≤ 3 (n)

n=0     2(0) ≤ 3 (0)

n=1     2(1) ≤ 3 (1)

n=2     2(2) ≤ 3 (2)

n=5     2(5) ≤ 3 (5)

n=10   2(10) ≤ 3 (10)

c ≥ 3   n ≥ 1

Tavg(n) = 1 1/2n + 1
1 1/2n + 1 ≤ Cg(n)
1 1/2n + 1 ≤ 3 (n)
n=0     1 1/2(0) + 1 ≤ 3(0)
n=1     1 1/2(1) + 1 ≤ 3(1)
n=5     1 1/2(5) + 1 ≤ 3(5)
n=10   1 1/2(10 + 1 ≤ 3(10)
c ≥ 3   n ≥ 1

Big Omega

Tmax(n) = 5n+1

5n + 1 ≥ Cg (n)

5n + 1 ≥ 5 (n)

n = 0      5(0) + 1 ≥ 0

n = 1      5(1) + 1 ≥ 5(1)

n = 5      5(5) + 1 ≥ 5(5)

n = 10    5(10) + 1 ≥ 5(10)

c ≤ 5      n ≥ 1

Tmin(n) = 2n

2n + 1 ≥ Cg (n)

2n + 1 ≥ 2 (n)

n=0     2(0) ≥ 2 (0)

n=1     2(1) ≥ 2 (1)

n=2     2(2) ≥ 2 (2)

n=5     2(5) ≥ 2 (5)

n=10   2(10) ≥ 2 (10)

c ≤ 2   n ≥ 1

Tavg(n) = 1 1/2n + 1
1 1/2n + 1 ≤ Cg(1/n)
1 1/2n + 1 ≤ 2 (1/n)
n=0     1 1/2(0) + 1 ≥ 1(1/0)
n=1     1 1/2(1) + 1 ≥ 1(1/1)
n=5     1 1/2(5) + 1 ≥ 1(1/5)
n=10   1 1/2(10) + 1 ≥ 1(1/10)
c ≥ 2   n ≥ 1

Big Theta

Contoh 4 : Algoritma Program Indeks Nilai

Program indeks_nilai

Deklarasi

nilai : integer

indeks : char

Algoritma

input (nilai)

if (nilai ≥ 80) then

    indeks <- ‘A’

else if (nilai ≥ 70) AND (nilai ≤ 80) then

    indeks <- ‘B’

else if (nilai ≥ 55) AND (nilai ≤ 70) then

    indeks <- ‘C’

else if (nilai ≥ 50) AND (nilai ≤ 55) then

    indeks <- ‘D’

else

    indeks <- ‘E’

end if

output (indeks)

end.

Operasi Dasar	Tmax(n)	Tmin(n)	Tavg(n)
<-	5n	n	1/2(5n-n)
≥	4n	n	1/2(4n-n)
≤	3n	n	1/2(3n-n)
input	n	n	0
output	n	n	0

Operasi dasar yang paling penting adalah (<-)

Tmax(n) = 5n + 4n + 3n + n + n

                Tn =  4n = n

-Big-oh(O)

Tn =  ≤ Cg(n)

4n≤ 5(n)

4.1 ≤ 5(1)        ;n=1

4 ≤ 5                ;C=5

T_max­_­(n)= 4n = O (n) untuk n ≥ 1 dan C ≥ 5

Jadi Tn= 4n termasuk kedalam himpunan Big-oh(O)

-Big -Omega (Ω)

Tn =  ≥ Cg(n)

4n ≥ 1(n)

4.2 ≥ 1(1)             ;n=2

8 ≥ 1                     ;C=1

T_max­_­(n)= 4n= Ω(n) untuk n ≤ 2 dan C  ≤ 1

Jadi Tn= 4n tidak termasuk ke dalam himpunan -Big -Omega (Ω)

-Big -Teta Θ

Karena T_max­_­(n)=4n=O(n) dan T_max­_­(n)= 4n = Ω(n) maka T_max­_­(n)= 4n= Θ(n)

Tmin(n) = n + n + n + n + n

                Tn = n

-Big-oh(O)

Tn =  ≤ Cg(n)

n ≤ 2(n)

1 ≤ 2(1)        ;n=1

1 ≤ 2             ;C=2

T_min­_­(n)= n = O (n) untuk n ≥ 1 dan C ≥ 2

Jadi Tn= n termasuk kedalam himpunan Big-oh(O)

-Big -Omega (Ω)

Tn =  ≥ Cg(n)

n ≥ 1/2(n)

1 ≥ 1/2(1)             ;n=1

1 ≥  1/2                 ;C=1/2

T_min­_­(n)= n= Ω(n) untuk n ≤ 1 dan C  ≤ 1/2

Jadi Tn= n tidak termasuk ke dalam himpunan -Big -Omega (Ω)

-Big -Teta Θ

Karena T_min­_­(n)= n=O(n) dan T_min­_­(n)= n= Ω(n) maka T_min­_­(n)= n= Θ(n)

Tavg(n) = 1/2(5n-n) + 1/2(4n-n) + 1/2(3n-n) + 0 + 0

                2 n + 1 1/2 n + n + 0 + 0

                Tn = 2 n = n

-Big-oh(O)

Tn =  ≤ Cg(n)

2n ≤ 3(n)

2.1 ≤ 3(1)        ;n=1

2 ≤ 3                ;C=3

T_avg­_­(n)= 2n = O (n) untuk n ≥ 1 dan C ≥ 1

Jadi Tn= 2n termasuk kedalam himpunan Big-oh(O)

-Big -Omega (Ω)

Tn =  ≥ Cg(n)

2n ≥ 1(n)

2.5 ≥ 1(5)              ;n=5

10 ≥ 5                ;C=1

T_avg­_­(n)= 2n= Ω(n) untuk n ≤ 5 dan C  ≤ 1

Jadi Tn= 2n tidak termasuk ke dalam himpunan -Big -Omega (Ω)

-Big -Teta Θ

Karena T_avg­_­(n)= 2n=O(n) dan T_avg­_­(n)= 2n= Ω(n) maka T_avg­_­(n)= 2n= Θ(n)