Page 14 - Chapter 5

 Simetris: menurut definisi urutan yang sama
 Misalkan f dan g adalah
fungsi yang domainnya merupakan (g dan f memiliki urutan yang sama iff f

+
himpunan bagian dari Z . Kita katakan adalah O (g) dan g adalah O (f))
bahwa f lebih rendah dari g atau f tumbuh  Transitif:

lebih lambat dari g jika
dukungan f dan g memiliki urutan yang sama
f adalah O (g) tapi g bukan O (f) | f (n) | <= c1 | g (n) | untuk semua n> = k1 (1)

| ( ) |
f n
lim  0 | g (n) | <= c2 | f (n) | untuk semua n> = k2 (2)
g n
n | ( ) |
dukungan g dan h memiliki urutan yang sama

 Contoh 4 | g (n) |<= c3 | h (n) | untuk semua n> = k3 (3)

5
7
f (n) = n , g(n) = n | h (n) |<= c4 | g (n) | untuk semua n> = k4 (4)
Jelas, | f (n) | <= c1 | g (n) | <= c1c3 | h (n) | untuk

7
5
f (n) adalah O (g), karena n <=n , n> = 1 semua n> = max (k1, k3)
Dukungan g (n) adalah O (f), maka | h (n) | <= c4 | g (n) | <= c2c4 | f (n) | untuk

ada c dan k sedemikian rupa semua n> = max (k2, k4)

5
7
n <=cn , for n>=k Jadi, f dan h memiliki urutan yang sama

2
Pilih N sehingga N> k dan N > c, lalu  Contoh 5
7
5
2
7
5
N <=cN < N N = N Semua fungsi yang memiliki
Ini adalah kontradiksi. urutan yang sama dengan g (n) =
n3 dikatakan berorde Θ (n3).

 Kita mendefinisikan relasi Θ, big Perintah umum dalam aplikasi ilmu

theta, pada fungsi yang komputer adalah

domainnya merupakan himpunan Θ (1), Θ (lg (n)), Θ (n), Θ (nlg (n)), Θ (n2),

bagian dari Z + sebagai f Θ g jika Θ (n3), dan Θ (2n)

dan hanya jika f dan g memiliki catatan:

urutan yang sama. Θ (1): kelas fungsi konstan

 Teorema 1: lg adalah fungsi log basis 2

Relasi Θ adalah relasi ekivalensi

Bukti: Refleksif: | f (n) | <= c | f (n) | , c = 1

untuk semua n> = 1