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