menghitung notasi asimtotik

Procedure faktorial (input  N : integer,output  Fak :  real)

{I.S. : harga N sudah terdefinisi}

{F.S. : menghasilkan harga faktorial dari N}

Kamus:

     I : integer {pencacah}

Algoritma:

     If  (N=0) or (N=1)

          Then

                Fak  ←   1

           Else

                Fak  ←   1

                For i ← 2 to N do

                     Fak ← Fak * i

                Endfor

     Endif

endprocedure

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

Tmin(n)    = 1

Tmax(n)    = 3n

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

= 4/2n

= 2n

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

t min(n)=n

-Big oh(O)

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

1≤1(1)

1≤2(2)

1≤3(3)

c=3

n0=n

-Big omega(Ω)

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

1 ≥ 1(1)

1 ≥2(2)

n0 =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))

3n≤1(1)

3n≤2(2)

3n≤3(3)

n0 =n

c =3

-Big omega(Ω)

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

3n ≥ 1(1)

3n ≥ 2(2)

n0 =n

c =2

-big theta(θ)

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

batas atas

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

2n ≤ 1 ≤3n

n0 =n

c1 =3

batas bawah

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

2n≤1≤3n

     n0 =n

c2 =3

untuk t average

T avg(n)=3+n/n

t(n)=2n

-Big oh(O)

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

1≤1(1)

1≤2(2)

1≤3(3)

n0 =n

c =3

-Big omega(Ω)

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

1≥ 1(1)

1≥ 2(2)

n0 =2

c =2

-big theta(θ)

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

batas atas

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

2n ≤ 1 ≤3n

n0 =n

c1 =3

batas bawah

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

2n ≤ 1 ≤3n

 n0 =n

c2 =3

notasi asimtotik

1 Program NamaBulan;
Kamus:
  bulan : integer
Algoritma:
  output('Masukkan kode bulan : ')
  input(bulan)
     if (bulan = 1) then

       output('Januari')
     else
     if (bulan = 2) then
       output('Februari')
     else
     if (bulan = 3) then
        output('Maret')
     else
     if (bulan = 4) then
        output('April')
     else
     if (bulan = 5) then
        output('Mei')
     else
     if (bulan = 6) then
        output('Juni')
     else
     if (bulan = 7) then
        output('Juli')
     else
     if (bulan = 8) then
        output('Agustus')
    else

    if (bulan = 9) then
       output('September')
    else
    if (bulan = 10) then
       output('Oktober')
    else
    if (bulan = 11) then
       output('November')
    else
    if (bulan = 12) then
       output('Desember')
    else
       output('Tidak ada pilihan')

end.

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

T min(n)= 0
T max(n)= 1
T avg(n)=0+1
                 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))
Tmin ≤ Cg(n)
0 ≤ n
n0 = 0
c = n

-Big omega(Ω)
T(n)≥ Ω (g(n))
Tmin ≥ Cg(n)
0 ≥ -n
n0 = 0
c = -n

-big theta(θ)
 C1(g(n)) ≤ T(n) ≤ C2(g(n))

batas atas
 C1(g(n)) ≤ T(n)
n ≤ 0
n0 = 0
c1 = n

batas bawah
 T(n) ≤ C2 (g(n))
-n ≤ 0
 n0 = 0
c2 = -n


untuk t max
t max(n)=3n
-Big oh(O)
T(n)≤O (g(n))
1 ≤ 1 (n)
n0 = 1
c = 1

-Big omega(Ω)
T(n)≥ Ω (g(n))
1 ≥ -1n
n0 = -1
c = 0

-big theta(θ)
 C1(g(n)) ≤ T(n) ≤ C2 (g(n))

batas atas
 C1(g(n)) ≤ T(n)
n  ≤ 1
n0 = n
c1 = 1

batas bawah
 T(n) ≤ C2 (g(n))
-n ≤ 1
 n0 = -n
c2 = 1


untuk t average

T avg(n)=n+3n = 2n
                  2
t(n)=2n
-Big oh(O)
T(n) ≤ O (g(n))
1/2 ≤ 1n
n0  = 1
c = 1

-Big omega(Ω)
T(n)≥ Ω (g(n))
1/2 ≥ -1n
n0 = -1n
c = -1

-big theta(θ)
 C2(g(n)) ≤ T(n) ≤ C1 (g(n))

batas atas
 C2(g(n)) ≤ T(n)
1/2 ≤ -n
n0 = 1
c1 = -n

batas bawah
 T(n) ≤ C1 (g(n))
1/2 ≤ -n
 n0 = 1
c2 = n

notasi asimtotik

2.Algoritma Merubah_waktu

KAMUS
J,m : integer

ALGORITMA
Input (j)
Input (m)

If m > 0 then
  Detik <−j * 3600
Else
  Detikß (j * 3600) + (m * 60)
Konversi <− detik / 60
Output ( konversi )

Menghitung input :
Tmax(n) = n+2
Tmin(n) = 1
Tavg(n) = (2n+1) = 3n = 3 n = n
                                  2             2       2
Big oh : t(n) < cg(n)

Tmax (n) =  n+2
                    n+2 < n+n (untuk semua n > 2)
                    n+2 < 3n
                    3n < 3n2
                    c=3n n0=2

Tmin (n) = 1 < 1

Tavg (n) = 2n+1
                 2n+1 < 2n+n (untuk semua n > 1)
                 2n+1 < 3n
                 3n < 3n2
                      c=3n n0=1

Big omega: t(n) > cg(n)
Tmax (n) = n+2 € O(n2)
                   n+2 > n+n (untuk semua n > 1)
                    n+2 > n
                    n > 12
                 c=1 n0=1

Tmin (n) = 1 > 0

Tavg (n) = 2n+1
                 2n+1 > 2n+n (untuk semua n > 0)
                 2n+1 >3n
                 3n < 3n
                 c=3n n0=0


Big Theta :c2g(n)< t(n) < c1g(n)
Tmax(n)    c2g(n)< n+2  < c1g(n)
            n+2  > 3n, n>2
            n+2  < 1, n>2
           c1=1, c2=3, n0=2

Tmin(n)    1 > 0

Tavg(n)    c2g(n)< 2n+1  < c1g(n)
            2n+1  > 3, n>1
            2n+1  < 3n, n>1
           c1=3, c2=3, n0=1

notasi asimtotik

3.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)
n0 =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)
n0 =n
c =3

-Big omega(Ω)
T(n)≥ Ω (g(n))
7 ≥ 1(1)
7 ≥ 2(2)

n0 =n
c =2

-big theta(θ)
 C1(g(n)) ≤ T(n) ≤ C2 (g(n))

batas atas
 C1(g(n)) ≤ T(n)
2n ≤ 7 ≤3n
n0 =n
c1 =3

batas bawah
 T(n) ≤ C2 (g(n))
2n≤7≤3n
 n0 =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)
n0 =n
c =3
-Big omega(Ω)
T(n)≥ Ω (g(n))
  7≥ 1(1)
7≥ 2(2)
n0 =2

c =2

-big theta(θ)
 C2(g(n)) ≤ T(n) ≤ C1 (g(n))

batas atas
 C2(g(n)) ≤ T(n)
2n ≤ 7 ≤3n
n0 =n
c1 =3

batas bawah
 T(n) ≤ C1 (g(n))
2n ≤ 7 ≤3n
 n0 =n
c2 =3

Procedure faktorial (input  N : integer,output  Fak :  real)

{I.S. : harga N sudah terdefinisi}

{F.S. : menghasilkan harga faktorial dari N}

Kamus:

     I : integer {pencacah}

Algoritma:

     If  (N=0) or (N=1)

          Then

                Fak  ←   1

           Else

                Fak  ←   1

                For i ← 2 to N do

                     Fak ← Fak * i

                Endfor

     Endif

endprocedure

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

Tmin(n)    = 1

Tmax(n)    = 3n

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

= 4/2n

= 2n

programpenjumlahanderet

Deklarasi

   N    : integer

   I    : integer

   jumlah  : integer

Algoritma

Read ( N )

   jumlahß 0

   iß 1

   whilei<Ndo

    jumlahßjumlah + 1

    kßI + 1

   endwhile

   ( I> N )

Write (jumlah)

a.Operasipengisiannilai

SINTAK	JUMLAH
jumlahß 0	1
iß 1	1
jumlahßjumlah + 1	N
ißi + 1	N
I >N	1
TOTAL	3 + 2n

b. operasipenjumlahan

SINTAK	JUMLAH
jumlahßjumlah + 1	N
i ßi + 1	N
TOTAL	2n

C. operasiperbandimgan

SINTAK	JUMLAH
I >N	1
TOTAL	1

Total kebutuhanwaktueksekusialgoritmapenjumlahanderet :

Total Waktu = t1 + t2 + t3 = (3 + 2n)a + (2n)b + c

RUNNING TIMEpenjumlahanderet

                                                               

programpeluncuranroket

Deklarasi

   I    : integer

   Algoritma

   iß 100

   while i >0 do

write (i)

iß 1 – 1

endwhile

    (I <0 )

   Write (‘GO!’)

a.Operasipengisiannilai

SINTAK	JUMLAH
Iß100	1
I >0	1
I ß1-1	N
I <0	1
TOTAL	3 +N

  

b..Operasipengurangan

SINTAK	JUMLAH
I ß1-1	N
TOTAL	N

c.Operasiperbandimgan

SINTAK	JUMLAH
I >0	1
I <0	1
TOTAL	2

Total kebutuhanwaktueksekusialgoritmapeluncuranroket

Total Waktu = t1 + t2 + t3 = (3 + n)a + (n)b +(2) c

RUNNING TIMEpeluncuranroket