Mencari T(n) dari Pseudocode Bilangan Prima

Procedure Bilangan_Prima

{I.S.: User memasukan nilai n}

{F.S.: Menampilkan hasil bilangan prima}

kamus:

n,i,j : integer

bPrima : Boolean

Algoritma:

input(n)

i ← 0 

j ← 0

for i ← 2 to n do

 if(n mod i=0)

  then

   j ← j +1

 endif

endfor

 if (j = 2) 

  bPrima ← true

   else

  bPrima ← false

endif

end.

Menghitung TMax, TMin, dan TAvg

Operasi Dasar	C(n)
←	n+3
=	n
+	n

( if ) min =1

      max = n

( for ) min =1

      max = n

Menghitung notasi О(Big Oh), Ω(Big Omega), dan Θ(Big Theta)

Tmin(n)  = 1 + 3 =4

Tmax(n) = n + 3

TAvg(n)  =   4 + 5 + 6 +...+(n+3)  ≈ n

                                n

Tmin(n) = 4

- О(Big Oh)

О = t(n) € О(g(n)) ; t(n) ≤ Cg(n)

         4 € О (1)

no = 0

c  = 1

- Ω(Big Omega)

Ω = t(n) € (g(n)) ; t(n) ≥ Cg(n)

         4 € О (1)

no = 0

c  = 1

- Θ(Big Theta)

Θ = t(n) € Θ (g(n)) ; C₂g(n) ≤ t(n) ≤ C₁g(n)

Batas atas     = 6 € О (1)

Batas Bawah  = 6 € Ω (1)

no = 0

c1  = 1 ; c2  = 1

Tmax(n) = n + 3

- О(Big Oh)
О = t(n) € О(g(n)) ; t(n) ≤ Cg(n)

      n + 3  ≤ 3n

×          3  ≤ 0                   → n = 0

×          4  ≤ 3                   → n = 1

(b)        5  ≤ 6                   → n = 2

(b)        6  ≤ 9                   → n = 3

(b)     103  ≤ 300               → n = 100

(b)   1.003 ≤ 3000             → n = 1.000

no = 2

c  = 3 

- Ω(Big Omega)
Ω = t(n) € (g(n)) ; t(n) ≥ Cg(n)

      n + 3 ≥ n

(b)        3  ≥ 0                   → n = 0

(b)        4  ≥ 1                   → n = 1

(b)        5  ≥ 2                   → n = 2

(b)       6  ≥ 3                   → n = 3

(b)     103 ≥ 100               → n = 100

(b)  1.003 ≥ 1.000             → n = 1.000

no = 0

c  = 1 

- Θ(Big Theta)

Θ = t(n) € Θ (g(n)) ; C₂g(n) ≤ t(n) ≤ C₁g(n)

Batas Atas = n + 3 ≤ 3n   = no = 2, c1  = 3 

Batas Bawah = n + 5 ≥ n = no = 0,  c2 = 1

no = 2, c1 = 3, c2 = 1

Tavg  (n)          = 4 + 5 + 6 . . . + (n + 3)
                                             n

                            = ½ n ( 4 + (n + 3 ))/n

                            = ½ (n+7)

                            = n/2 + 7/2 

- О(Big Oh)
О = t(n) € О(g(n)) ; t(n) ≤ Cg(n)

      ½n + 7/2 € О(n)

      ½n + 7/2 ≤ 2n

×            7/2 ≤ 0          → n = 0

×              4 ≤ 2           → n = 1

×           9/2 ≤ 4           → n = 2

(b)            5 ≤ 6           → n = 3

(b)      107/2 ≤ 200       → n = 100

(b)      1007 ≤ 2000       → n = 1000

no = 3

c  = 2

- Ω(Big Omega)
Ω = t(n) € (g(n)) ; t(n) ≥ Cg(n)

      ½n + 7/2 € Ω(n)

      ½n + 7/2  ≥ ½ n

(b)            7/2  ≥ 0          → n = 0

(b)              4   ≥ 1/2        → n = 1

(b)             9/2 ≥ 1           → n = 2

(b)               5  ≥ 3/2        → n = 3

(b)          107/2 ≥ 50         → n = 100

(b)        1.007/2 ≥ 500       → n = 1000

no = 0

c  =  ½

- Θ(Big Theta)
Θ = t(n) € Θ (g(n)) ; C₂g(n) ≤ t(n) ≤ C₁g(n)

Batas Atas  =  ½n + 7/2   ≤   2n   = no = 3, c1  = 2 

Batas Bawah =  ½n + 7/2 ≥ ½n   = no = 0,  c2  = ½

no = 3, c1 = 2, c2 = ½