渐近符号：证明大欧米茄，O和θ

Question

我有一些渐近记号问题，我并没有完全掌握。

因此，当证明渐进复杂性时，我理解找到常数的操作以及表示法正确的n0项。因此，例如：

Prove 7n+4 = Ω(n)

在这种情况下，我们将选择一个常数c，因此对于大欧米茄，它小于7。选择6将导致

7n+4 >= 6n

n+4 >= 0

n = -4

但是由于n0不能为负项，我们选择一个正整数，所以n0 = 1。

但是像这样的问题呢？

Prove that n^3 − 91n^2 − 7n − 14 = Ω(n^3).

我选择1/2作为常数，达到

1/2n^3 - 91n^2 - 7n -14 >= 0。

但是我不确定如何继续。另外，我想关于theta这样的问题：

Let g(n) = 27n^2 + 18n and let f(n) = 0.5n^2 − 100. Find positive constants n0, c1 and c2 such
that c1f(n) ≤ g(n) ≤ c2f(n) for all n ≥ n0.

在这种情况下，我在这里执行两个单独的操作，一个大O比较和一个大Omega比较，因此存在theta关系或紧密关系？如果是这样，我将如何处理？

Answer 1

为了显示n ³-91n ²-7n-14在Ω（n ³）中，我们需要显示一些数字n ₀和c，使得，对于所有n≥n ₀：

n ³-91n ²-7n-14≥cn ³

您选择了c = 0.5，所以让我们开始吧。重新排列给出：

n ³-0.5n ³≥91n ² + 7n + 14

将两边都乘以2并简化：

182n ² + 14n + 28≤n ³

对于所有n≥1，我们有：

182n ² + 14n + 28≤182n ² + 14n ² + 28n ² = 224n ²

并且当n≥224时，我们有224n ²≤n ³。因此，选择n ₀ = 224和c = 0.5证明了原始函数在Ω（n ³）中。