Page 13 - Chapter 5

  Misalkan f dan g adalah fungsi yang domainnya

+
merupakan himpunan bagian dari Z . Kita mengatakan
bahwa f dan g memiliki urutan yang sama jika f adalah O

(g) dan g adalah O (f).

f adalah O (g): f tumbuh tidak lebih cepat dari g

g adalah O (f): g tumbuh tidak lebih cepat dari f

| ( ) |
f n
c  lim  c , c c  R
2
g n
n | ( ) | 1 1 2

 Contoh 3
4 2 4
Misal f (n) = 3n -5n and g(n) = n didefinisikan untuk

bilangan bulat positif n. Kemudian f dan g memiliki urutan

yang sama. Pertama,

3n  5n  3n  5n  3n  5n  8 , n  1
4
4
4
4
2
2
4
n if

Misalkan c = 8 dan k = 1, maka | f (n) | <= c | g (n) | untuk
semua n> = k. Jadi f adalah O (g). Sebaliknya,
n  3n  2n  3n  5 , n  2
2
4
4
4
4
n
f
i

Misalkan c = 1 dan k = 2, kita punya g adalah O (f).