algorithm - 数据结构 : time cost, 大 O 表示法

Question

For large problems sizes, an algorithm with time cost O(2^n) is faster than an algorithm that has time cost O(N^2)

这是真的还是假的？

我的想法是，如果 C^n，C = 常数且 C > 1，那么它的增长速度会比O(N^2)。这是正确的吗？

Answer 1

Yes, c^n grows faster than n^2, if c>1
if c=1 then c^n =1
if c<1 then c^n "decays"

Proof for c>1
let t(n) = (c^n)/(n^2)
now lim n-> infinity t(n) = (By L'Hospitals Rule) = lim (d/dn c^n) / lim(d/dn n^2)
= lim (d/dn c^n lg n) / lim(d/dn 2n)    
= lim (d/dn c^n lg n * lg n) / lim(d/dn 2)
-> infinity.

所以根据 http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations 中描述的属性，我们说 n^2 增长较慢。