大哦符号证明O(2^n)的
答
只需使用
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)
。
答
我们可以使用大哦符号的定义来解决这个问题,如下所示:
提示:(1)2 ^(N + 10)= 1024×2^N。 (2)对于所有n> = 1,2^n +n≤2^(n + 1)。 –