大O表示法，证明3N^2 + 3N - 30 = O(N^2)为真

Question

我想用基本的算术推理出来：

问题：

3N^2 + 3N - 30 = O(N^2)证明这是真的。

我目前拥有的：

T(N) = 3N^2 + 3N - 30

我必须找到 c 和 n0，其中 t(N) <= c (N^2) 对于所有 N >= n0 来证明该陈述是正确的。我将 3N^2 + 3N - 30 替换为 3N^2 + 3N^2 - 30N^2 因为这是 >= 3N^2 + 3N - 30 。

3N^2 + 3N^2 - 30N^2 对于所有 N>=1 都是 -24N^2 。因此 c = -24 和 n0 = 1 证明语句确实是 = O(N^2)

这是正确的吗？如果不是，我应该怎么做才能使其正确？

问题：证明 3N^2 +3N - 20 = omega (N^2)

我目前拥有的：

仍在尝试先找到 c 和 n0。 3N^2 +3N -20 >= N^2 因此 c 为 1 且 n0 为 1 证明此语句确实等于 omega (N^2)

Answer 1

对于问题 2，设 n_0:=10 和 c:=2。让n>=n_0。通过不等式链

3n^2 + 3n - 20 >= 3n^2 - 20
               >= 3n^2 - 100
               >= 3n^2 - n^2
                = 2n^2
                = cn^2

我们得到了想要的结果。

Big O notation, prove that 3N^2 + 3N - 30 = O(N^2) is true