Growth function question and solution

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

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

Tags: growth function