Notasi Asimtotik - Kasus 3

Kasus 3

a.       Kasus Terbaik (T _min(n))

T_min(n) =  1

b.      Kasus Terburuk (T _max(n))

T _max(n) =  n

c.       Kasus Rata-rata T _avg(n)

T _avg(n) = n

Penyelesaian :

Notation Asimtotik

a.       Kasus Terbaik  (T _min(n))

T_min(n) = 1

Misalkan : T_min(n) = T(n)

Maka : T(n) = 1

1.      Big Oh (O)

Untuk semua  n > n₀

Dimana  C (kostanta) dan  n₀  (batas  n ), nilainya bebas ditentukan.

Cari c dan n₀, sehingga  T(n)  <  C * g(n) untuk semua n  >  n₀  dari kasus dibawah ini.

1 Є O(n)

misal :

n = 1

  

Jadi

1 Є O(n) adalah benar, jika C = 4,  n₀ = 1

2.      Big Omega (Ω)

Untuk semua  n > n₀

Dimana  C (kostanta) dan  n₀  (batas  n ), nilainya bebas ditentukan.

Cari c dan n₀, sehingga  T(n)  >  C * g(n) untuk semua n  >  n₀  dari kasus dibawah ini.

1 Є  Ω (n⁰)

Misal :

n = 0

  

Jadi

1  Є  Ω(n⁰) adalah benar, jika C = 1, n₀ = 0

3.      Big Theta (Θ)

Untuk semua  n > n₀

Dimana  C (kostanta) dan  n₀  (batas  n ),  nilainya bebas ditentukan.

Cari c₁, c₂,  dan n₀, sehingga  C₂*g(n) <  T(n)  < C₁*g(n)  untuk semua n  >  n₀  dari kasus dibawah ini.

1  Є  Θ(n⁰)

misal :

n = 1

Jadi 

N – 1 Є Θ(n) adalah benar, jika C₁ = 1, C₂ = ½, n₀ = 1

b.      Kasus Terburuk (T _max(n))

T _max(n) =  n

Misalkan : T_max(n) = T(n)

Maka : T(n) = n

1.      Big Oh (O)

Untuk semua  n > n₀

Dimana  C (kostanta) dan  n₀  (batas  n ), nilainya bebas ditentukan.

Cari c dan n₀, sehingga  T(n)  <  C * g(n) untuk semua n  >  n₀  dari kasus dibawah ini.

n  Є O(n)

misal :

n = 0

  

Jadi

n  Є O(n) adalah benar, jika C = 5, n₀ = 0

2.      Big Omega (Ω)

Untuk semua  n > n₀

Dimana  C (kostanta) dan  n₀  (batas  n ), nilainya bebas ditentukan.

Cari c dan n₀, sehingga  T(n)  >  C * g(n) untuk semua n  >  n₀  dari kasus dibawah ini.

n  Є  Ω (n)

Misal :

n = 0

  

Jadi

n  Є  Ω(n) adalah benar, jika C = 1, n₀ = 0

3.      Big Theta (Θ)

Untuk semua  n > n₀

Dimana  C (kostanta) dan  n₀  (batas  n ),  nilainya bebas ditentukan.

Cari c₁, c₂,  dan n₀, sehingga  C₂*g(n) <  T(n)  < C₁*g(n)  untuk semua n  >  n₀  dari kasus dibawah ini.

n  Є  Θ(n)

misal :

n = 0

Jadi 

n   Є Θ(n) adalah benar, jika C₁ = 2, C₂ = ½, n₀ = 0

c.       Kasus Rata-rata T _avg(n)

T _avg(n) = n

Misalkan : T_avg(n) = T(n)

Maka : T(n) = n

1.      Big Oh (O)

Untuk semua  n > n₀

Dimana  C (kostanta) dan  n₀  (batas  n ), nilainya bebas ditentukan.

Cari c dan n₀, sehingga  T(n)  <  C * g(n) untuk semua n  >  n₀  dari kasus dibawah ini.

n  Є O(n)

misal :

n = 0

  

Jadi

n  Є O(n) adalah benar, jika C = 2, n₀ = 0

2.      Big Omega (Ω)

Untuk semua  n > n₀

Dimana  C (kostanta) dan  n₀  (batas  n ), nilainya bebas ditentukan.

Cari c dan n₀, sehingga  T(n)  >  C * g(n) untuk semua n  >  n₀  dari kasus dibawah ini.

n  Є  Ω (n)

Misal :

n = 0

  

Jadi

n  Є  Ω(n) adalah benar, jika C = 1, n₀ = 0

3.      Big Theta (Θ)

Untuk semua  n > n₀

Dimana  C (kostanta) dan  n₀  (batas  n ),  nilainya bebas ditentukan.

Cari c₁, c₂,  dan n₀, sehingga  C₂*g(n) <  T(n)  < C₁*g(n)  untuk semua n  >  n₀  dari kasus dibawah ini.

n  Є  Θ(n)

misal :

n = 0

 

Jadi 

                        n²   Є Θ(n) adalah benar, jika C₁ = 5/4, C₂ =5/6, n₀ = 0