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