Démontrer ou réfuter n^2 - n + 2 ∈ O (n)

Question

Pour mon cours d'analyse d'algorithme, j'ai dérivé d'un algorithme la fonction f (n) = n^2 - n + 2. Maintenant je dois prouver ou réfuter f (n) ∈ O (n). Évidemment, ce n'est pas le cas, alors j'ai essayé de réfuter cela pendant quelques heures et je n'arrive pas à comprendre comment le faire.

Pour réfuter, je dois prouver le contraire:

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

J'ai essayé de travailler en arrière et en avant, mais ne peut pas sembler obtenir partout. J'ai aussi essayé de prouver que, contre mon jugement, f (n) ∈ O (n):

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

... sans succès. Que fais-je si horriblement mal?

Answer 1

Il a été un certain temps, mais au moins ce n'est pas grand-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

Qu'en est-il une preuve par contradiction. Réglez vos cas généraux de telle sorte que vous essayez de montrer que c'est vrai, et ensuite par une déclaration qui doit être fausse dans chaque cas, alors la preuve entière doit être fausse.

Answer 3

suppose qu'il y a un certain C> 0 et M> 0 tel que pour tout n> M,

n^2 - n + 1 < = Cn pour tout n> M

division par n

n - 1 + 1/n = < C pour tout n> M

et ainsi

n-1 = C < pour tout n> M.

ce qui n'est pas possible.