术语 f(n) = 2^(n+5) + n^2 和 g(n) = 2^(n+1) - 1 的大 O 符号

Question

我有：

• () = 2⁺⁵ + ²
• () = 2⁺¹ - 1

我必须证明是否：

• () = Ω(()) or/and
• () = O(())

我知道您不需要确认 () 中的 ² 或 () 中的 -1 因为 2⁺⁵ 和 2⁺¹ 的复杂度更高。但我不太确定如何找出下限和上限。

我的方法是说 () 中的 +5 和 () 中的 +1 不会改变任何复杂性，这意味着上述两个陈述都是正确的并且 () = θ （（））。但是我没有办法证明这一点。

Answer 1

我们有

• () = 2⁺⁵ + ²
• () = 2⁺¹ − 1

() = Ω(()) 为真，当我们可以找到一个 () ≥ ⋅()) 对于任何大于所选的 ₀.

我们看到即使 =1 和 ₀=0 也是如此。

() = O(()) 为真，当我们可以找到一个 () ≤ ⋅()) 对于任何大于所选的 ₀:

2⁺⁵ + ² ≤ (2⁺¹ − 1)

让我们选择 = 2⁵，然后我们必须证明足够大：

2⁺⁵ + ² ≤ 2⁵(2 ⁺¹ − 1)

2⁺⁵ + ² ≤ 2⋅2⁺⁵ − 32

² ≤ 2⁺⁵ − 32

我们可以看到对于所有大于 1 的值都是如此。