Page 15 - Chapter 5

 Contoh 6 7. Jika h adalah fungsi bukan nol dan Θ (f)

Setiap fungsi logartmik f (n) = logb (n) lebih rendah dari (atau sama dengan) Θ

memiliki urutan yang sama dengan g (n) = lg (g), maka Θ (fh) lebih rendah dari (atau

(n). Ada identitas perubahan basis logaritmik sama dengan Θ (gh))

log ( ) x
log ( ) x  a 8. Jika Θ (f) lebih rendah dari Θ (g), maka
b
log ( ) b Θ (f + g) = Θ (g)
a

di mana loga (b) adalah konstanta. Jadi
1
| log ( ) | x | lg( ) |," "holds  Contoh 7

n
b
| lg( ) | Tentukan kelas Θ dari masing-masing
b
Dan sebaliknya, berikut ini

n 

| lg( ) | lg( ) | log ( ) |," "holds (a) f(n) = 4n -6n +24n
b
n
7
3
4
b
Oleh karena itu g adalah O (f) dan f adalah O (b) g(n) = lg(n) -3n
15
n
(g) (c) h(n) = 1.1 +n
7
 Aturan untuk menentukan Kelas (a) Θ(f) = Θ(n ) (Rules 3,6 and 8)
Θ dari suatu Fungsi (b) Θ(g)= Θ(n) (Rules 2,6 and 8)

n
1. Θ (1) fungsi konstan dan memiliki (c) Θ(h)= Θ(1.1 ) (Rules 5 and 8)

pertumbuhan nol, pertumbuhan paling

lambat.  Contoh 8

k
2. Θ (lg (n)) lebih rendah dari Θ (n ) jika Dengan menggunakan aturan untuk

k> 0 mengurutkan kelas, susunlah yang berikut

b
3. Θ (na) lebih rendah dari Θ (n ) iff b> a> dalam urutan dari yang terendah ke yang
0 tertinggi

0.2
2
4. Θ (an) lebih rendah dari Θ (b ) iff b> a> Θ(nlg(n)) Θ(100n -n) Θ(n )
n
n
7
0 Θ(1,000,000) Θ(1.3 ) Θ(n+10 )
5. Θ (nk) lebih rendah dari Θ (a ) untuk
n
7
0.2
semua daya nk dan a> 1 Θ(1,000,000) , Θ(n ), Θ(n+10 ) , Θ(nlg(n)),
2
n
6. Jika r bukan nol, dan Θ (rf) = Θ (f) Θ(100n -n) Θ(1.3 )
1.2
untuk fungsi apapun f Θ(n ) ?