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

すべての n > M に対して、

n^2 - n + 1 <= Cn for all n > M

nで割る

n - 1 + 1/n <= C for all n > M

など

すべての n > M に対して n-1 <= C。

これは不可能です。

Answer 3

矛盾による証明はどうですか。あなたがそれが真であることを示しようとしているようにあなたの一般的なケースを設定し、そして次にそれぞれの場合に偽でなければならないステートメントによって、それから全体の証明は偽でなければなりません。