Notasi Asimtotik - Kasus 2

Kasus 2

T_min(n) = 1

T_max(n) = ²log n

T_avg(n) = (sulit ditemukan untuk binary search)

Penyelesaian :

            1.      T_min(n) = 1

a.       1 ∈ O(g(n))

Cari c dan n₀, sehingga t(n) ≤ cg(n) untuk semua n ≥ n₀

1 ≤ n (untuk semua n ≥ 1)

C = 1, n₀ = 1

 

b.      1 ∈ Ω(g(n))

  Cari c dan n₀, sehingga t(n) ≥ cg(n) untuk semua n ≥ n₀

  1 ≥ n (1 ∉ Ω(g(n)))

  Jadi, 1 ∉ Ω(g(n))

c.       1 ∈ Θ(g(n))

  Cari c dan n₀, sehingga c₂g(n) ≤ t(n) ≤ c₁g(n) untuk semua n ≥ n₀

  Karena salah satu dari notasi tidak termasuk (1 ∉ Ω(g(n))), maka 1 ∉ Θ(g(n))

            2.      T_max(n) = ²log n

 

a.       1 ∈ O(g(n))

  Cari c dan n₀, sehingga t(n) ≤ cg(n) untuk semua n ≥ n₀

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

  C = 1, n₀ = 0

b.      1 ∈ Ω(g(n))

  Cari c dan n₀, sehingga t(n) ≥ cg(n) untuk semua n ≥ n₀

  ²log n ≥ n (²log n ∉ Ω(g(n)))

  Jadi, ²log n ∉ Ω(g(n))

c.       1 ∈ Θ(g(n))

  Cari c dan n₀, sehingga c₂g(n) ≤ t(n) ≤ c₁g(n) untuk semua n ≥ n₀

  Karena salah satu dari notasi tidak termasuk (²log n ∉ Ω(g(n))), maka ²log n ∉ Θ(g(n))

      

      3.      T_avg(n) = (sulit ditemukan untuk binary search)

Notasi Asimtotik - Kasus 4

Kasus 4

T_min(n) = n

T_max(n) = n

T_avg(n) = n

Penyelesaian :

           1.      T_min(n) = n

a.        n ∈ O(g(n))

  Cari c dan n₀, sehingga t(n) ≤ cg(n) untuk semua n ≥ n₀

  n ≤ 2n (untuk semua n ≥ 0)

  c = 2, n₀ = 0

b.       n ∈ Ω(g(n))

  Cari c dan n₀, sehingga t(n) ≥ cg(n) untuk semua n ≥ n₀

  n ≥ ½n (untuk semua n ≥ 0)

  c = ½, n₀ = 0

c.        n ∈ Θ(g(n))

  cari c dan n₀, sehingga sehingga c₂g(n) ≤ t(n) ≤ c₁g(n) untuk semua n ≥ n₀

  Batas atas

  n ≤ 2n (untuk semua n ≥ 0)

  Batas bawah

  n ≥ ½n (untuk semua n ≥ 0)

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

            2.      T_max(n)=n

a.       n ∈ O(g(n))

  Cari c dan n₀, sehingga t(n) ≤ cg(n) untuk semua n ≥ n₀

  n ≤ 3n (untuk semua n ≥ 0)

  c = 3, n₀ = 0

b.      n ∈ Ω(g(n))

  Cari c dan n₀, sehingga t(n) ≥ cg(n) untuk semua n ≥ n₀

  n ≥ ¼ n (untuk semua n ≥ 0)

  c = ¼ , n₀ = 0

c.        n ∈ Θ(g(n))

  cari c dan n₀, sehingga sehingga c₂g(n) ≤ t(n) ≤ c₁g(n) untuk semua n ≥ n₀

  Batas atas

  n ≤ 3n (untuk semua n ≥ 0)

  Batas bawah

  n ≥ ¼ n (untuk semua n ≥ 0)

  c₁ = 3, c₂ = ¼ , n₀ = 0

             3.      T_avg(n) = n

a.       n ∈ O(g(n))

  Cari c dan n₀, sehingga t(n) ≤ cg(n) untuk semua n ≥ n₀

  n ≤ 4n (untuk semua n ≥ 0)

  c = 4, n₀ = 0

b.      n ∈ Ω(g(n))

  Cari c dan n₀, sehingga t(n) ≥ cg(n) untuk semua n ≥ n₀

  n ≥  1/8n (untuk semua n ≥ 0)

  c = 1/8, n₀ = 0

c.        n ∈ Θ(g(n))

  cari c dan n₀, sehingga sehingga c₂g(n) ≤ t(n) ≤ c₁g(n) untuk semua n ≥ n₀

  Batas atas

  n ≤ 4n (untuk semua n ≥ 0)

  Batas bawah

  n ≥ 1/8n (untuk semua n ≥ 0)

  c₁ = 4, c₂ = 1/8, n₀ = 0

Notasi Asimtotik - Kasus 1

Kasus 1

T_min(n) = 1

T_max(n) = n

T_avg(n) = n

Penyelesaian :

           1.      T_min(n) = 1

a.      O ( Big Oh )

  1 ∈ O(g(n))

  Cari c dan n₀, sehingga t(n) ≤ cg(n) untuk semua n ≥ n₀

  1 ≤ n (untuk semua n ≥ 1)

  C = 1, n₀ = 1

b.      Ω ( Big Omega )

  1 ∈ Ω(g(n))

  Cari c dan n₀, sehingga t(n) ≥ cg(n) untuk semua n ≥ n₀

  1 ≥ n (1 ∉ Ω(g(n)))

  Jadi, 1 ∉ Ω(g(n))

c.       Θ( Big Theta )

  1 ∈ Θ(g(n))

  Cari c dan n₀, sehingga c₂g(n) ≤ t(n) ≤ c₁g(n) untuk semua n ≥ n₀

  Karena salah satu dari notasi tidak termasuk (1 ∉ Ω(g(n))), maka 1 ∉ Θ(g(n))

          2.      T_max(n) = n

a.      O ( Big Oh )

  n ∈ O(g(n))

  Cari c dan n₀, sehingga t(n) ≤ cg(n) untuk semua n ≥ n₀

   n ≤ 2n

  n ≤ 2n (untuk semua n ≥ 0)

  c = 2, n₀ = 0

b.      Ω ( Big Omega )

  n ∈ Ω(g(n))

  Cari c dan n₀, sehingga t(n) ≥ cg(n) untuk semua n ≥ n₀

   n ≥ ½n

  n ≥ ½n (untuk semua n ≥ 0)

  c = ½ , n₀ = 0

c.       Θ ( Big Theta )

  n ∈ Θ(g(n))

  cari c dan n₀, sehingga sehingga c₂g(n) ≤ t(n) ≤ c₁g(n) untuk semua n ≥ n₀

  Batas atas

  n ≤ 2n

  n ≤ 2n (untuk semua n ≥ 0)

  c_{1 =}  2, n_{0 =}  0

  Batas bawah

  n ≥ ½n

  n ≥½ n (untuk semua n ≥ 0)

  c_{2 =  1/2}, n_{0 =}  0

  Jadi :

  c₁ = 2, c₂ = ½, n_{0 =} 0

          3.      T_avg(n) = n

a.      O ( Big Oh )

  n ∈ O(g(n))

  Cari c dan n₀, sehingga t(n) ≤ cg(n) untuk semua n ≥ n₀

   n ≤ 3n

  n ≤ 3n (untuk semua n ≥ 0)

  c = 3, n₀ = 0

b.      Ω ( Big Omega )

  n ∈ Ω(g(n))

  Cari c dan n₀, sehingga t(n) ≥ cg(n) untuk semua n ≥ n₀

   n ≥  1/8n

  n ≥  1/8n (untuk semua n ≥ 0)

  c = 1/8, n₀ = 0

c.       Θ ( Big Theta )

  n ∈ Θ(g(n))

  cari c dan n₀, sehingga sehingga c₂g(n) ≤ t(n) ≤ c₁g(n) untuk semua n ≥ n₀

  Batas atas

  n ≤ 3n

  n ≤ 3n (untuk semua n ≥ 0)

  c_{1 =} 3_,  n_{0 =} 0

  Batas bawah

  n ≥  1/8n

  n ≥ 1/8n (untuk semua n ≥ 0)

  c₂₌1/8 , n_{0 =}  0

Jadi :

  c₁ = 3, c₂ = 1/8, n₀= 0

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