大哦符号证明O（2^n）的

Question

我修改我的老算法分析笔记接受记者采访时，

我注意到一个问题，我无法弄清楚当我学习

证明2n+10 + n = O(2n)

任何帮助将是伟大的！

Answer 1

只需使用

 
f(n) ∈ O(g(n))  ⇔  lim supn → ∞ |f(n)/g(n)| < ∞ 

这导致你

 
lim supn → ∞ |(2n+10 + n)/(2n)| = lim n → ∞ |(210 ⋅ 2n + n)/(2n)| 
           = lim n → ∞ |(210 ⋅ 2n)/(2n) + (n)/(2n)| 
           = 210 < ∞ 

事实上，你也可以证明2n ∈ O(2n+10 + n)以同样的方式，你会得到2n+10 + n ∈ Θ(2n)。

Answer 2

我们可以使用大哦符号的定义来解决这个问题，如下所示：