big-o - 证明或反证 n^2 - n + 2 ∈ O(n)

Question

在我的算法分析课程中，我从算法推导出函数 f(n) = n^2 - n + 2。现在我需要证明或反驳f(n) ∈ O(n)。显然不是，所以我一直试图反驳这一点几个小时，但不知道该怎么做。

为了反驳它，我需要证明否定：

∀M > 0, ∀N > 0, ∃n > N s.t. n^2 - n + 1 < M·n

我试过前后工作，但似乎无处可去。我还试图证明，根据我的判断，f(n) ∈ O(n)：

∃M > 0, ∃N > 0 s.t. ∀n > N, n^2 - n + 1 ≥ M·n

...没有成功。我在做什么如此可怕的错误？

Answer 1

已经有一段时间了，但至少它不是大θ...

f(n) ∈ O(g(n) <--> (∃c,m>0) | (∀n>m) 0 < f(n) <= cg(n)

let f(n) = n^2 - n + 2
let g(n) = n

(∃c,m>0) | (∀n>m) 0 < n^2 - n + 2 <= cn
(∃c,m>0) | (∀n>m) 0 < n^2 - n <= cn
(∃c,m>0) | (∀n>m) 0 < n^2 <= cn + n
(∃c,m>0) | (∀n>m) 0 < n^2 <= 2cn + n
(∃c,m>0) | (∀n>m) 0 < n^2 <= (2c+1)n

let C = 2c+1

(∃C,m>0) | (∀n>m) 0 < n^2 <= Cn
(∃C,m>0) | (∀n>m) 0 < n <= C

(∃C,m>0) | (∀n>m) 0 < n <= C

There is no constant C s.t. 0 < n <= C for all sufficiently large n.
Therefore, n^2 - n + 2 is not O(n)

Answer 2

假设有一些 C> 0 和 M > 0 使得对于所有 n > M，

n^2 - n + 1 <= Cn 对于所有 n > M

除以 n

n - 1 + 1/n <= C 对于所有 n > M

所以

对于所有 n > M，n-1 <= C。

这是不可能的。

Answer 3

反证法呢。设置你的一般情况，以便你试图证明它是真实的，然后通过一个在每种情况下都必须是错误的陈述，那么整个证明必须是错误的。