Sebagaimana kemarin kita telah membahas tentang kompleksitas Algoritma, kali ini kita akan membahas lebih dalam lagi dengan menggunakan Notasi Asimtotik.
Notasi Asimtotik Algoritma Bubble Sort (Ascending)
Worse
Case :
Tmax(n)
= 12 + 18n + 15n²
a. O
– Nation
t(n) ≤ cg(n)
12 + 18n + 15n² = O(n²)
12
+ 18n + 15n² ≤ 12n² + 18n² + 15n²
12
+ 18n + 15n² ≤ 45n² (untuk semua n ≥ 1)
c = 45, n0 = 1
b. Omega
– Nation
t(n) ≥ cg(n)
12 + 18n + 15n² = Ώ(n²)
12 + 18n + 15n² ≥ n² (untuk semua n
≥ 0)
c = 1, n0 = 0
c. Theta
– Nation
c2g(n) ≤ t(n) ≤ c1g(n)
Batas
Atas = 12 + 18n + 15n² ≤ 45n²; c
= 45, n0 = 1
Batas
Bawah = 12 + 18n + 15n² ≥ n²; c =
1, n0 = 0
Jadi, c1= 45, c2=
1, n0 = 1
Best
Case :
Tmin(n) = 3 – 8n
+ 6n²
d. O
– Nation
t(n) ≤ cg(n)
3 – 8n + 6n² = O(n²)
3
– 8n + 6n² ≤ 3n² + 8n² + 6n²
3
– 8n + 6n² ≤ 17n² (untuk semua n ≥ 1)
c = 17, n0 = 1
e. Omega
– Nation
t(n) ≥ cg(n)
3 – 8n + 6n² = Ώ(n²)
3 – 8n + 6n² ≥ n² (untuk semua n ≥
0)
c = 1, n0 = 0
f. Theta
– Nation
c2g(n) ≤ t(n) ≤ c1g(n)
Batas
Atas = 3 – 8n + 6n²≤ 45n²; c = 17,
n0 = 1
Batas
Bawah = 3 – 8n + 6n² ≥ n²; c = 1,
n0 = 0
Jadi, c1= 17, c2= 1, n0 = 1
Average Case :
Tavg(n)
= 21n²+10n+15
2
g. O
– Nation
t(n) ≤ cg(n)
21n²+10n+15 /
2= O(n²)
21n²+10n+15
/ 2 ≤ 21n² + 10n² + 15n² / 2
21n²+10n+15
/ 2 ≤ 46n² / 2 = 23n² (untuk
semua n ≥ 1)
c = 23, n0 = 1
h. Omega
– Nation
t(n) ≥ cg(n)
21n²+10n+15 /
2 = Ώ(n²)
21n²+10n+15 /
2 ≥ n² / 2 (untuk semua n ≥ 0)
c = ½ , n0 = 0
i.
Theta – Nation
c2g(n) ≤ t(n) ≤ c1g(n)
Batas
Atas = 21n²+10n+15 / 2; c = 23, n0 = 1
Batas
Bawah = 21n²+10n+15 / 2; c = ½, n0 = 0
Jadi, c1= 23, c2= ½,
n0 = 1
Notasi
Asimtotik Algoritma Selection Sort Maximum
Worst Case :
Tmax(n)
= -3 + 4n²
a. O
– Nation
t(n) ≤ cg(n)
-3 + 4n²= O(n²)
-3
+ 4n² ≤ n² + 4n²
-3
+ 4n² ≤ 5n² (untuk semua n ≥ 0)
c = 5, n0 = 0
b. Omega
– Nation
t(n) ≥ cg(n)
-3 + 4n² = Ώ(n²)
-3 + 4n² ≥ n² (untuk semua n ≥ 1)
c = 1, n0 = 1
c. Theta
– Nation
c2g(n) ≤ t(n) ≤ c1g(n)
Batas
Atas = -3 + 4n² ≤ 5n²; c = 5, n0 = 0
Batas
Bawah = -3 + 4n² ≥ n²; c = 1, n0 = 1
Jadi, c1= 5, c2= 1, n0 = 1
Best Case :
Tmin(n)
= -4 + 2n + 3n²
d. O
– Nation
t(n) ≤ cg(n)
-4 + 2n + 3n² = O(n²)
-4
+ 2n + 3n² ≤ 3n² + n²
-4
+ 2n + 3n² ≤ 4n² (untuk semua n ≥ 0)
c = 4, n0 = 0
e. Omega
– Nation
t(n) ≥ cg(n)
-4 + 2n + 3n² = Ώ(n²)
-4 + 2n + 3n² ≥ n² (untuk semua n ≥
1)
c = 1, n0 = 1
f. Theta
– Nation
c2g(n) ≤ t(n) ≤ c1g(n)
Batas
Atas = -4 + 2n + 3n² ≤ n²; c = 4,
n0 = 0
Batas
Bawah = -4 + 2n + 3n² ≥ n²; c =
1, n0 = 1
Jadi, c1= 4, c2= 1, n0 = 1
Average Case :
Tavg(n)
= 7n²+2n-7
2
g. O
– Nation
t(n) ≤ cg(n)
7n²+2n-7
/ 2 = O(n²)
7n²+2n-7
/ 2 ≤ 7n² + n²
7n²+2n-7
/ 2 ≤ 8n² / 2 = 4n² (untuk semua n ≥ 0)
c = 4, n0 = 0
h. Omega
– Nation
t(n) ≥ cg(n)
7n²+2n-7
/ 2 = Ώ(n²)
7n²+2n-7
/ 2 ≥ n² / 2 (untuk semua n ≥ 1)
c = ½ , n0 = 1
i.
Theta – Nation
c2g(n) ≤ t(n) ≤ c1g(n)
Batas
Atas = 7n²+2n-7 / 2 ≤ 8n² / 2 = 4n²; c = 4, n0 = 0
Batas
Bawah = 7n²+2n-7 / 2 ≥ n² / 2; c = ½, n0 = 1
Jadi, c1= 4, c2= ½,
n0 = 1
