显示n^2不是O（n * log（n））？

Question

仅使用O（）的定义？

Answer 1

你需要用反证法来证明。假设n^2是O(n*log(n))。根据定义意味着有一个有限的和非可变实数c使得

n^2 <= c * n * log(n) 

每n大于一些有限数量n0。

然后你到达的时候点c >= n /log(n)，你推导出n -> INF，c >= INF这显然是不可能的。

你断定n^2不O(n*log(n))

Answer 2

你要计算的

(n * log(n))/(n^2) = 
= log(n)/n = 
= 0 if n approaches infinity. 

的限制，因为log(n)增长高于n慢。