Page 12 - Chapter 5

 Misalkan f dan g adalah

fungsi yang domainnya merupakan himpunan bagian dari

+
Z . Kita katakan bahwa f adalah O (g), dibaca f besar-Oh dari g,
jika ada konstanta c dan k sehingga | f (n) | <= c | g (n) | untuk

semua n> = k.

Jika f adalah O (g), maka f tumbuh tidak lebih cepat dari g.

| ( ) |
f n
lim  c , c R

g n
n | ( ) |

 Contoh 2
2 3
Fungsi f (n) = ½ n3 + ½ n adalah O (g) untuk g (n) = n . Untuk

melihat ini, pertimbangkan

1 n  1 n  1 n  1 n  n if 1
, n 
3
2
3
3
3
2 2 2 2

Memilih 1 untuk c dan 1 untuk k, kita telah menunjukkan bahwa |

f (n) | <= c | g (n) | untuk semua n> = 1 dan f adalah O (g).

5.3 Pertumbuhan

Fungsi