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)