Kali ini saya akan membahas bagaimana cara mencari Nilai Asimtotik dari T(n) yang sudah kita dapatkan sebelumnya
Output = 8 Misal A
Input = 2 Misal B
Jumlah Operasi
←= 12 Misal C
+ = 4 Misal D
* = 2n Misal E
> = n Misal F
Maka :
T(n) = (8)A + (2)B + (12)C + (4)D + (2n)E + (n)F
- Mencari O-notation
T(n) ϵ O(g(n))jika
T(n) ≤ c.g(n)
T(n) ≤ c.g(n) = (8)A + (2)B + (12)C + (4)D + (2n)E + (n)F ≤ c.g(n)
pengecekan jika n = 1, c = 18
= 8 + 2 + 12 + 4 + (2n) + (n) ≤ 18.1
= 8 + 2 + 12 + 4 + (2.1) + (1) ≤ 18.1
= 29 ≤ 18
Kondisi pengecekan menggunakan n = 1 dan c = 18 ternyata salah.
Pengecekan Lain
T(n) ≤ c.g(n) = (8)A + (2)B + (12)C + (4)D + (2n)E + (n)F ≤ c.g(n)
pengecekan jika n = 10, c = 18
= 8 + 2 + 12 + 4 + (2.10) + (10) ≤ 18.10
= 8 + 2 + 12 + 4 + 20 + 10 ≤ 180
= 56 ≤ 180
Kondisi pengecekan menggunakan n = 1 dan c = 18 ternyata benar
- Mencari Omega-notation
T(n) ϵ Ω(g(n))
jika
T(n) ≥ c.g(n).
T(n) ≥ c.g(n) = (8)A + (2)B + (12)C + (4)D + (2n)E + (n)F ≥ c.g(n)
pengecekan jika n = 1, c = 1
= 8 + 2 + 12 + 4 + (2n) + (n) ≥ 1.1
= 8 + 2 + 12 + 4 + (2.1) + (1) ≥ 1.1
= 29 ≥ 1
Kondisi pengecekan menggunakan n = 1 dan c = 1 ternyata benar
Pengecekan Lain
T(n) ≥ c.g(n) = (8)A + (2)B + (12)C + (4)D + (2n)E + (n)F ≥ c.g(n)
pengecekan jika n = 2, c = 1
= 8 + 2 + 12 + 4 + (2n) + (n) ≥ 2.1
= 8 + 2 + 12 + 4 + (2.2) + (2) ≥ 2.1
= 32 ≥ 2
Kondisi pengecekan menggunakan n = 2 dan c = 1 ternyata benar
-Theta-notation
T(n) ϵ ϴ(g(n))
jika
c2.g(n) ≤ T(n) ≤ c1.g(n)
c2.g(n) ≤ T(n) ≤ c1.g(n) = c2.g(n) ≤ (8)A + (2)B + (12)C + (4)D + (2n)E + (n)F ≤ c1.g(n)
pengecekan jika n = 1, c = 1
= 1.1 ≤ 8 + 2 + 12 + 4 + (2n) + (n) ≤ 1.1
= 1 ≤ 8 + 2 + 12 + 4 + (2.1) + (1) ≤ 1
= 1 ≤ 29 ≤ 1
Kondisi pengecekan menggunakan n = 1 dan c = 1 ternyata salah
Pengecekan Lain
c2.g(n) ≤ T(n) ≤ c1.g(n) = c2.g(n) ≤ (8)A + (2)B + (12)C + (4)D + (2n)E + (n)F ≤ c1.g(n)
pengecekan jika n = 10, c2 = 1, c1 = 18
= 1.10 ≤ 8 + 2 + 12 + 4 + (2n) + (n) ≤ 18.10
= 10 ≤ 8 + 2 + 12 + 4 + (2.10) + (10) ≤ 180
= 10 ≤ 56 ≤ 180
Kondisi pengecekan menggunakan n = 10, c2 = 1 dan c1 = 18 ternyata benar
Terima Kasih ^_^!
