Problems

Prove the big-Oh equations, showing graphs of the proof ideas, and exact values for c and x₀, or using the limit.

1. Show x = O(x+7) and x+7 = O(x).
2. Show 3x+2 = O(x).
3. Show 0 = O(1) but 1 is not O(0).
4. Show x² = O(2^x) but 2^x is not O(x²).
   Hint: Two things you might try. First, put everything in the exponent by writing x as 2^{log x}.
   Second, did you ever notice that exponentiation is really respectful of size? That is x ≤ y exactly when 2^x ≤ 2^y.
5. Show 2^x = O(3^x) but 3^x is not O(2^x).
6. Show x² = O(x³) but x³ is not O(x²). show x² + 10 x + 100 = O(x³).
   Hint: This might be easy to show without any hints. But if not, think about which x make x² ≥ 10 x, and what x make x² ≥ 100. And then what x make the messy sum thus less than 3 x². And who cares about that anyway?
7. Show aⁿ = O(n!) for all a ≥1, but n! is not O(aⁿ) for any a.
   For this problem, n is restricted to integers.
8. Suppose you have three functions, f, g, and h, and f is bigger than both: g = O(f) and h = O(f). Show (prove) that f is bigger than the function that takes the sum of g and h at every x, g + h = O(f).
9. Show how the result of problem 8 can be applied to solve the big-Oh result requested in problem 6.
10. Find two eventually positive functions, f and g, such that:
    1. f = O(g) and
    2. the limit f(x)/g(x) as x goes to infinity does not exist.
    For the limit not to exist, it would mean that the ratio goes to infinity, or that the ratio never settles down to tending to a value.
    What does this mean for ratio tests for big-Oh?
11. Suppose f and g are eventually positive functions and the limit f(x)/g(x) is c as x goes to infinity, where c > 0.
    What is the big-Oh relationships between f and g, if there are any?
    What does this mean for ratio tests for big-Oh?