Question

For my algorithm analysis course, I ve derived from an algorithm the function f(n) = n^2 - n + 2. Now I need to prove or disprove f(n) ∈ O(n). Obviously it s not, so I ve been trying to disprove that for a few hours and can t figure out how to do it.

To disprove it, I need to prove the negative:

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

I ve tried working backwards and forwards, but can t seem to get anywhere. I ve also tried to prove that, against my judgment, f(n) ∈ O(n):

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

... with no success. What am I doing so horribly wrong?

Answer 1

It s 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

Assume there is some C> 0 and M > 0 such that for all n > M,

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

Divide by n

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

and so

n-1 <= C for all n > M.

which is not possible.

Answer 3

What about a proof by contradiction. Set up your general cases such that you are trying to show it is true, and then by an statement which must be false in each case, then the whole proof must be false.

友情链接