n ^ 1.001对n*log n/log 2的大O？

Question

这个问题让我陷入了困境,我希望StackOverflow能够提出这个问题.问题是问题

n^1.001 = O(n log n) (log is base 2)

换句话说,n log n的增长速度是否快于n ^ 1.001.

我一直在这个圈子里四处走动.我绘制了n ^ 1.001 vs log n(我取出了n,因为n在等式的两边).在我的程序崩溃之前,我将它们绘制到大约10 ^ 32左右,甚至到那里,n ^ 0.001甚至没有达到2,而log n要大得多.然而,我想知道,并且无法证明任何一种方式,最终,n ^ 1.001将会比n log n更快地开始增长,因为它的指数大于1.

它是否正确？哪个有更大的增长功能？

Answer 1

想想以下事实:

n^(1/2) > log(n) for n > 10,
n^(1/4) > log(n) for n > 100,
n^(1/8) > log(n) for n > 10000, etc.

这很容易推断出来n^? > log(n) for all ? > 0, n sufficiently large.希望有帮助!