Доказать или опровергнуть n ^ 2 - n + 2 ∈ O (n)

Question

Для моего курса анализа алгоритма я вывел из алгоритма функцию f (n) = n ^ 2 - n + 2. Теперь мне нужно доказать или опровергнуть f (n) ∈ O (n).Очевидно, что это не так, поэтому я пытался опровергнуть это в течение нескольких часов и не могу понять, как это сделать.

Чтобы опровергнуть это, мне нужно доказать отрицательное:*

Я пытался работать вперед и назад, но, похоже, никуда не деться.Я также пытался доказать, что вопреки моему мнению, f (n) ∈ O (n):

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

... безуспешно.Что я делаю так ужасно неправильно?

Answer 1

Предположим, что существует некоторое 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 2

Это было давно, но, по крайней мере, это не большая тета ...

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 3

А как насчет доказательства от противного? Установите ваши общие случаи так, чтобы вы пытались показать, что это правда, а затем с помощью утверждения, которое должно быть ложным в каждом случае, тогда все доказательство должно быть ложным.