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

Tag: big-o , proof Author: jlw530 Date: 2010-09-27

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?

Should not N also appear in the "s.t. part" somewhere?

Best Answer

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)

comments:

Close, but not quite. You're assuming n ? cn ? c ? 1, which doesn't rule out the 0 < c < 1 case. But if you replace C = 2c by C = c+1, then it works.
Thanks for the help!

Other Answer1

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.

Other Answer2

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.