MEMBUKTIKAN NOTASI ASIMTOTIK ( BIG OH,BIG OMEGA, BIG THETA)

1. procedure kali_matriks(d,e,f : integer; a,b : matriks; input c : matriks)

kamus

   x,y,z  : integer

algoritma

   for x ←1 to d do

     for y ←1 to f do

       for z ←1 to e do

       c[x,y] ← c[x,y] + a[x,z]*b[z,y]

       endfor

     endfor

   endfor

Tmin = 1

Tmax = 3n

RUMUS Big Omega (O)

T(n) ≤ c.g(n)

Tmin (n) = 1

1 ≤ 1 n (dengan n ≥ 1)

1 ≤ 1 (1)

1 ≤ 1

c = 1, n₀ = 1, maka Tmin (n) adalah anggota dari Big O

Tmax(n) = 3n

n ≤ n (dengan n ≥ 3n)

0 ≤ 0

c = n, n₀ = 0, maka Tmax (3n) adalah anggota dari Big O

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

(1 + 3n)/2  ≤ n(1 + 3n)/2

((1)+3(1))/2 ≤ (1)((1)+3(1))/2

2≤2

c = (1+3n)/2 , n₀ = 1, maka Tavg (n) adalah anggota dari Big O

2. procedure jumlah_matriks(output k,l : integer; A : matriks; input jumlah : integer)

kamus

   m,n : integer

algoritma

    jumlah ← 0

    m ← 1

    for m ←1 to k do

      for n ← 1 to l do

        jumlah ← jumlah + a[m,n]

      endfor

    endfor

Tmin = n

Tmax = 2+n

3. function hargakamar ( kamar : string) → integer;

  if  (kamar='KELAS III')

    then

    hargakamar ← 120000

    else

       if  (kamar='KELAS II')

          then

          hargakamar ← 190000

          else

             if (kamar='KELAS I')

                then

                hargakamar ← 300000

                else

                   if (kamar='VVIP')

                       then

                       hargakamar ← 550000

                       else

                          if (kamar='VIP')

                             then

                             hargakamar ← 450000

                            else

                               if (kamar='SVIP')

                                  then

                                  hargakamar ← 650000;

                               endif

                              endif

                      endif

               endif

        endif  

end function

Tmin = 1

Tmax = 6

RUMUS Big Omega (Ω)

T(n) ≥ c.g(n)

Tmin (n) = 1

1 ≥ 1 n (dengan n ≥ 0)

1 ≥ 1 (0)

1 ≥ 0

c = 1, n₀ = 0, maka Tmax (n) adalah anggota dari Big Ω

Tmax (n) = 6

6 ≤ 6 n (dengan n ≥ 1)

6 ≤ 6 (1)

6 ≤ 6

c = 6, n₀ = 1, maka Tmax (n) adalah anggota dari Big O

Tavg (n) = 7/2 ≤ n(7/2)

4. Menentukan_indeksNilai;

Kamus

nama, matkul : string

nilai : byte

indeks : char

Algoritma

     input(nilai)

       if (nilai>85) and (nilai<100)

           then

           indeksß'A'

           else

            if (nilai>75) and (nilai<84)

               then

                indeksß'B'

                else

                   if (nilai>60) and (nilai<74)

                      then

            indeksß'C'

                      else

                      if (nilai>45) and (nilai<59)

                         then

                            indeksß'D'

                         else

                              indeksß'E'

                      endif

                   endif

            endif

       endif  

       output(indeks)

Tmin = 1
Tmax = 5

5. menghitung_harga_total

kamus

   belanja : real

   diskon : real

   harga_total : real

algoritma

     input(belanja)

           if belanja > 100000 then

                        diskon  ← belanja*0.25

                        harga_total  ← belanja – diskon

                    else then

                   if belanja < 100000 then

                        output('Harga Total = Rp.', belanja)

                   endif

           endif

     output(diskon)

     output(harga_total)

Tmin = 2

Tmax = 3