Bagaimana membuktikannya

Ini pertanyaan pekerjaan rumah dari buku Udi Manber. Setiap petunjuk akan menyenangkan :)

Saya harus menunjukkan bahwa:

$n(\log_3(n))^5 = O(n^{1.2})$

Saya mencoba menggunakan Teorema 3.1 buku:

(untuk c > 0 , a > 1 )$f(n)^c = O(a^{f(n)})$$c > 0$$a > 1$

Substituasi:

$(\log_3(n))^5 = O(3^{\log_3(n)}) = O(n)$

tetapi $n(\log_3(n))^5 = O(n\cdot n) = O(n^2) \ne O(n^{1.2})$

Terima kasih atas bantuannya.

$a = (3^{0.2})$

Alasan bahwa apa yang Anda lakukan tidak berhasil adalah sebagai berikut. Batas besar oh tidak ketat; sementara logaritma ke kelima memang besar-oh dari fungsi linear, juga besar oh dari fungsi root kelima. Anda membutuhkan hasil yang lebih kuat ini (yang juga bisa Anda dapatkan dari teorema) untuk melakukan apa yang Anda lakukan.

$(\log_3(n))^5$$O(n^{0.2})$$\log_3(n)$$O(n^{0.04})$

$\alpha$