41
f
(n) adalah
?( g (n)) ,
maka
fungsi
g
(n) memiliki
nilai
pertambahan
waktu
yang
lebih
besar dari
f
(n) .
Notasi
?
menyatakan batas bawah dari kompleksitas waktu dari suatu
instruksi.
Jika
f
(n) adalah
?( g (n)) dan
jika
terdapat
suatu
riil
konstan
c
>
0
dan
sebuah
nilai
positif
integer
n
0
,
sehingga
f
(n) = c.g (n) untuk
semua
n
>
n
0
,
yang
artinya
jika
f
(n) adalah
O( g (n)) ,
maka
fungsi
g
(n) memiliki
nilai
pertambahan
waktu
yang
lebih
kecil dari
f
(n) . Misalkan dapat dilihat beberapa teorema di bawah ini :
?
Teorema 1
Jika
f
(n) dan
g
(n) adalah kompleksitas waktu, maka berlaku :
1. f (n) adalah
T( f (n))
2. f (n) adalah
T( g (n)) jika dan hanya jika
g
(n) adalah
T( f (n))
3. jika
f
(n) adalah
T( g (n)) dan
g
(n) adalah
T(h(n)) , maka
f
(n) adalah
T(h(n))
?
Teorema 2
Jika
f
(n) dan
g
(n) adalah suatu fungsi kompleksitas waktu maka berlaku :
1. untuk semua
c
>
0
, fungsi
c. f (n) adalah
T( f (n))
2. jika
f1
(n)
adalah
T( g (n)) dan
f
2
(n)
adalah
T( f (n)) , maka
(
f1
+ f
2
)
(n) adalah
T( g (n))
3.
jika
f1
(n)
adalah
T( g
1
(n)) dan
f
2
(n)
adalah
T( g
2
(n)) ,
maka
(
f1 *
f
2
)
(n)
adalah
T( g
1
*
g
2
)
(n)
?
Teorema 3
Hubungan antara notasi
T, O, dan
?
1. f (n) adalah
?( g (n)) jika dan hanya jika
g
(n) adalah
O( f (n))
 |