Notasi Asimtotik - Kasus 5

Kasus 5

a.       Kasus Terbaik (T _min(n))

T_min(n) =  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) = n – 1

Misalkan : T_min(n) = T(n)

Maka : T(n) = 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.

n – 1 Є O(n)

misal :

n = 0

Jadi

 n – 1 Є O(n) adalah benar, jika C = 1, 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 – 1 Є  Ω (n⁰)

Misal :

n = 2

Jadi

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

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 – 1  Є  Θ(n)

misal :

n = 2

 

Jadi

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

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 = 3, 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 = 8

Jadi

 n²  Є  Ω(n) adalah benar, jika C = 8, n₀ = 8 

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, 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 = 3

Jadi

 n²  Є  Ω(n) adalah benar, jika C = 10/4, n₀ = 3 

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₂ =2/5, n₀ =0