Using the definition of O, prove each of the following by finding explicit integer constants C and k so that k is minimal for the given C

Question

a.) 9n + 77 = O(n) (find a C < 50) d.) 11n^2 + 75n + 84 = O(n^2) (find a C < 40)

NOTE: I am second year Java student and am currently in a Data Structures and Algorithms class. I have no idea how to do these problems (there are more but I figured two should give me a basis). What is O(n) and how does it differ from O(n^2)? My professor just said we should look at this stuff in the book because these questions will be similar to what are on our exams. I have no idea how to attack these problems. Please explain. I'm not looking for just a solution to copy down, but rather understanding.

Answer 1

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. https://xlinux.nist.gov/dads/HTML/bigOnotation.html is a definition. Here is a sketch of where to go with that and what it means without doing these problems for you. [I am deliberately leaving parts for you to figure out.] So if we are saying 9n+77=O(n) that mean there is a constant c such that for n big enough 9n+77<=Cn. The intuition here is that in the grand scheme of things 77 does not matter and 9n is basically what matters, and that is a multiple of n. But choosing the constant = 9 will not do because 9n+77 is actually > 9n always. I feel like anything bigger than 9 would do, but let us keep life simple and choose C=10. So we want 9n+77<=10n. Solve that and you will have your k that n must be >= to. 11n^2 + 75n + 84 = O(n^2) is intuitively true because in the long run the 11n^2 dwarfs everything else. Again, you would be tempted to pick C=11, but that will not quite do (why?). So you choose a bigger C and use it to say we want 11n^2+75n+84<=Cn^2. To find k, solve the inequality (choosing the part that looks like n>=the larger root of the corresponding quadratic equation). You may need to use the quadratic formula.