Advertisements

Growth function question and solution

23 May

Misalkan f (n) dan g (n) keduanya adalah fungsi bernilai real yang asimtotik positif dengan domain N. Buktikan atau sangkal pernyataan-pernyataan berikut:

1). Jika f (n) = O(g (n)) maka 2^f(n) = O(2^g(n))

Solusi: Karena f (n) dan g (n) keduanya asimtotik positif, maka f (n), g (n) ≥ 0

Pernyataan salah. Karena jika kita pilih f (n) = 2n dan g (n) = n. Jelas bahwa 2n = O(n).
Akan tetapi tinjau bahwa

2^(2n) =(2^2)^n = 4^n ≠ O(2^n) .

Andaikan 4^n = O(2^n), maka kita memiliki

growth function

2). f (n) = θ(f (n/2))

Solusi: Karena f (n) dan g (n) keduanya asimtotik positif, maka f (n), g (n) ≥ 0

Pernyataan salah. Jika f (n) = θ(f (n/2)) maka haruslah f (n) = O(f (n/2)).  Jika kita pilih f (n) = 2^n. Akan dibuktikan bahwa 2^n ≠ O (2^(n/2))


Andaikan 2^n = O (2^(n/2)), maka kita memiliki

growth function2

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: