Notasi Asimtotik dari worst case, best case, average case algoritma mencari bilngan prima

bil_prima

Deklarasi

 i,bil,b :interger

Algoritma

b←0

input(bil)

for i ←1 to bil do

                if (bil mod i = 0)

                                then

                                                b←b+1

                endif

endfor

                if b = 2 

                                then

                                                output(bil,”bilangan prima”)

                                else

                                                output(bil,”bukan bilangan prima”)

                endif

                

Worst case, Best case, Average case

T_min(n) = 2

O (Big Oh)     

      2   O (n⁰)

      2  ≤  3n⁰                   (untuk semua n ≥ 1)   

      c = 3 , n₀ = 1

    Ω (Big Omega)

      2   Ω (n⁰)

      2 ≥  n⁰             (untuk semua n ≥ 0)

      c = 1, n₀ = 0

    Θ (Big Theta)      

      2   Θ (n⁰)

      -  Batas atas

         2  ≤  3n⁰                (untuk semua n ≥ 1)   

      -  Batas bawah

         2 ≥  n⁰                   (untuk semua n ≥ 0)

      c₁ = 3,  c₂ = 1, n₀ = 1

    T_max(n) = n +1

    O (Big Oh)

      n + 1    O (n)

      n + 1  ≤  2n              (untuk semua n ≥ 1)

      c = 2, n₀ = 1

    Ω (Big Omega)

      n + 1   Ω (n)

      n + 1 ≥  n                 (untuk semua n ≥ 0)

      c = 1, n₀ = 0

    Θ (Big Theta)      

      n +1   Θ (n)

      -  Batas atas

         n + 1  ≤  2n           (untuk semua n ≥ 1)   

      -  Batas bawah

         n + 1 ≥  n              (untuk semua n ≥ 0)

      c₁ = 2,  c₂ = 1, n₀ = 1

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

      ≈  n+1 /2 

                    ≈ n

      O (Big Oh)

       2+(n+1)    O (n)

       2+(n+1)  ≤  3n           (untuk semua n ≥ 2)

       c = 3, n₀ = 2

      Ω (Big Omega)

       2+(n+1)    Ω (n)             

       2+(n+1)  ≥  2n                            (untuk semua n ≥ 0)

       c = 1, n₀ = 0

      Θ (Big Theta)

         2+(n+1)     Θ (n)     

         -  Batas atas

            2+(n+1)  ≤  3n             (untuk semua n ≥ 2)

         -  Batas bawah

            2+(n+1)  ≥  2n             (untuk semua n ≥ 0)

            c₁ = 3,  c₂ = 1, n₀ = 2