i need to proof that 2n^2 - 2n -7 = O(n^2), when the n is 1 or two i got negative value of f(n). i am not sure does the way i proof Big-O is correct.Your help and advice is highly appreciated.
f(n) = 2n^2 - 2n -7 = O(n^2) if c=2;
n=1->2(1)^2 - 2(1) -7 = -7 <= 2*(1)^2
n=2->2(2)^2 - 2(2) -7 = -3 <= 2*(2)^2
n=3->2(3)^2 - 2(3) -7 = 14 <= 2*(3)^2
The definition of Big-Oh has more to do with asymptotic behavior than local behavior. If your function went negative for increasing values of n, say it oscillated, there might be more of a concern. For this function, though, there is no problem: you are free to consider the function for all values greater than some n0 which you alone are allowed to choose. So, if the function going negative early on bothers you, write your proof such that those numbers aren't used. For example:
Base case: for n = 3, f(n) = 2*3*3 - 2*3 - 7 = 18 - 6 - 7 = 5 <= 9 * c = c * 3 * 3 = c * n^2. This is true provided that c >= 5/9.
Induction hypothesis: assume f(n) <= c * n^2 for all n starting at 3 up through k.
Induction step: we must show that f(k+1) <= c * (k+1)^2. We have f(k+1) = 2(k+1)^2 - 2(k+1) - 7 = 2k^2+4k+2 - 2k - 2 - 7 = 2k^2 + 2k - 7 < 2k^2 + 4k < 2k^2 + 4k + 2 = 2(k^2 + 2k + 1) = 2(k+1)^2, so the choice c = 2 works here.
In hindsight, it should be obvious that 2n^2 - 2n - 7 is always less than 2n^2 for positive increasing n.