tags:

views:

181

answers:

3

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?

+3  A: 

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)
mepcotterell
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.
Adam Rosenfield
Thanks for the help!
mepcotterell
+1  A: 

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.

spowers
+3  A: 

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.

Moron