Did I do this big-O notation correctly?

Question

It is for a homework assignment and I'm just getting thrown a little bit by the negative sign.

Express the following in terms of big-O notation. Use the tightest bounds possible. For instance, n5 is technically O(n1000), but this is not as tight as O(n5).

n² −500n−2

• n² - 500 n - 2
• <= n² - 500 n
• <= n² for all n > 0
• which is O(n²)

Answer 1

Yes O(n^2) is correct. The negative sign should not bother you. Yes, if n = 10, then it'd be a negative number, but what if the n is sufficiently large?

E.g. see these two graphs: link - n^2 for sufficiently large n is always larger than n^2-500n-2.

Answer 2

For Big O notation what you need to remember is that it only matters for some number x₀ and all numbers above that. Specifically f(x)= O(g(x)) as x approaches infinity if there is some number M and some real number x₀ such that |f(x)| <= M|g(x)| for all x >= x₀. (Source for equations, wikipedia).

Basically, we only need to consider large values of x and you can pick an arbitrarily large value. So large in fact that n^2 will overshadow a subtraction by 500n. To be more technical if I pick M to be 2 and x₀ to be 100000000000000000. Then the above equation holds. I'm being lazy and picking an x₀ that is extremely large but the equation lets me. For an M equal to 2 a much smaller value of x₀ would work, but again, it doesn't matter.

Finally, your answer of O(n^2) is correct