Homework #2

Here are some exercises dealing with the Big-Oh notation. The due date for this homework is Monday, April 12. You will be graded on whether you did the homework. It is in your best interest to do your best. Try to do these problems without consulting your notes. If you cannot, consult your notes, then try again. If you have questions, drop by office hours.

Big-oh exercises

1. Give the definition of f(n) = O( g(n) ).
2. Demonstrate, by applying the definition of big-oh, that
1. n² = O(n²)
2. n² + 1 = O(n²)
3. k n² + 1 = O(n²), where k is a positive constant
3. Demonstrate, by giving appropriate counterexamples, that the following claims are false:
1. If f(n) = O(g(n)) and f(n) = O(h(n)) then g(n) = h(n).
2. If f(n) = O(g(n)) and g(n) = O(f(n)) then f(n) = g(n).
4. Prove, by applying the definition of f(n) = O(g(n)), each of the following:
   1. If f(n) = O(g(n)) and g(n) = O(h(n)) then f(n) = O(h(n)).
   2. If f₁(n) = O(g₁(n)) and f₂(n) = O(g₂(n)) then f₁(n) f₂(n) = O(g₁(n)g₂(n))