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?
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)