證明給定函數等於O（N）

Question

我試圖證明，對於任何常數，k，log^k N = o(N)（小的N 2 O）

所有我知道的小o是它遵循的形式T(n) = o(p(n))哪裏T(n)的增長速度低於p(n)。此外，我不能真的做一個限制和使用L'hopital rule，因爲我不知道什麼f(n)或g(n)是。有人可以幫助我開始！

Answer 1

你需要證明

lim  (log^k N)/N = 0 
N -> infinity 

寫N = e^x，併成爲

lim (x^k)/(e^x) = 0 

現在，使用指數函數的冪級數展開，

e^x = ∑ (x^n)/n! 

得到該商的估計。

尾翼：與n = k+1採摘的項給出e^x > x^(k+1)/(k+1)!並從容易追隨(x^k)/(e^x) < (k+1)!/x。