Notasi Asimtotik dari Worst case, Best case, Average case Algoritma Menghitung Persegi

Menghitung_persegi

Deklarasi

I,j,n : integer

Algoritma

Input(n)

For i← 1 to n do

   For j← 1 to n do

         If (i>j)

                        then

                                    output(“*”)

                        else

                                    output(“ “)

               endif

     endfor

endfor

Worst case, Best case, Average case

T_min(n) = n²

O (Big Oh)

      n²    O (n²)

      n²  ≤  2n²                  (untuk semua n ≥ 0)

      c = 2, n₀ = 0

Ω (Big Omega)

      n²    Ω (n²)

      n²   ≥  ½ n²               (untuk semua n ≥ 1)

      c = ½ , n₀ = 1

Θ (Big Theta)      

      n²    Θ (n²)

      -  Batas atas

         n²  ≤  2n²         (untuk semua n ≥ 0)

      -  Batas bawah

         n²  ≥  ½ n²      (untuk semua n ≥ 1)

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

T_max(n) = n²

O (Big Oh)

      n²    O (n²)

      n²  ≤  2n²                  (untuk semua n ≥ 0)

      c = 2, n₀ = 0

Ω (Big Omega)

      n²    Ω (n²)

      n²   ≥  ½ n²               (untuk semua n ≥ 1)

      c = ½ , n₀ = 1

Θ (Big Theta)      

      n²    Θ (n²)

      -  Batas atas

         n²  ≤  2n²         (untuk semua n ≥ 0)

      -  Batas bawah

         n²  ≥  ½ n²      (untuk semua n ≥ 1)

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

T_avg(n) = n² ≈ n

O (Big Oh)

      n²    O (n²)

      n²  ≤  2n²                  (untuk semua n ≥ 0)

      c = 2, n₀ = 0

Ω (Big Omega)

      n²    Ω (n²)

      n²   ≥  ½ n²               (untuk semua n ≥ 1)

      c = ½ , n₀ = 1

Θ (Big Theta)      

      n²    Θ (n²)

      -  Batas atas

         n²  ≤  2n²         (untuk semua n ≥ 0)

      -  Batas bawah

         n²  ≥  ½ n²      (untuk semua n ≥ 1)

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