如何不用代码计算时间复杂度

Question

我必须证明(^正在崛起)：

1. n^2 = O(2^n)
2. n^2 = Θ(2^n)
3. 8^n = O(4^n)
4. 8^n = Ω(4^n)

是否有一种理论方法总是可以知道它是真还是false，并给出了演示？

Answer 1

这些是极限计算问题：

f(n) = O(g(n))   if and only if      lim (f(n)/g(n)) = 0
                                       n -> +inf

f(n) = Θ(g(n))   if and only if      lim (f(n)/g(n)) = some positive finite number
                                       n -> +inf 

f(n) = Ω(g(n))   if and only if      lim (f(n)/g(n)) = +inifinity
                                       n -> +inf 

或者，倒过来

Let x = lim(f(n)/g(n))
          n -> +inf

x = 0 ?                          then f(n) = O(g(n))
x = some postive finite number ? then f(n) = Θ(g(n)) 
x = +infinity ?                  then f(n) = Ω(g(n))

因此，我们必须计算极限，例如在第一种情况下：

 lim(n^2/2^n) = 0 (apply l'Hospital's rule twice)
   n -> +inf 

这就是为什么n^2 = O(2^n)等：

 n^2 = O(2^n)  - true
 n^2 = Θ(2^n)  - false, in fact O(2^n)
 8^n = O(4^n)  - false, in fact Ω(2^n) 
 8^n = Ω(4^n)  - true