大哦符號證明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

我們可以使用大哦符號的定義來解決這個問題，如下所示：