Prove or disprove n ^ 2 - n + 2 ∈ O (n)

Question

For my course in analyzing the algorithm, I got the function f (n) = n ^ 2 - n + 2 from the algorithm. Now I need to prove or disprove f (n) ∈ O (n) . Obviously, this is not so, so I tried to refute it for several hours and cannot figure out how to do it.

To disprove this, I need to prove a negative result:

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

I tried to work back and forth, but it seems I’m not going anywhere. I also tried to prove that, in my opinion, f (n) ∈ O (n):

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

... without success. What am I doing so terribly wrong?

Answer 1

It has been a while, but at least it's not big-theta ...

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-1 <= C n > M.

.

Answer 3

How about evidence from the contrary. Set up your general cases in such a way that you are trying to show that this is true, and then with a statement that must be false in each case, then all the evidence must be false.