Доказать или опровергнуть 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

насчет доказательства от противного. Настройте свои общие случаи таким образом, что вы пытаетесь показать, что это правда, а затем утверждением, которое должно быть ложным в каждом случае, тогда все доказательство должно быть ложным.

Answer 3

Предположим, что имеется некоторая С> 0 и М> 0, что для всех п> М,

п^2 - п + 1 < = Сп для всех п> М

Деление на п

п - 1 + 1/п < = С при всех п> M

и так

п-1 < = C для всех п> М.

который невозможно.