Homework 10 (assigned August 22, due August 29)

This homework assignment covers the material in sections 3.2 and 3.5 of the textbook.

1. Do problems 25, 26, and 28 on page 127. (Each problem is worth 4 points.)

2. Do problems 39, 41, 44, 48 (hard), and 50 on page 151. (Each problem is worth 4 points.)

3. Find the least integer n such that f(x) is O(xⁿ) for the functions:
   (1) f(x) = 2x² + x³lg x
   (2) f(x) = 3x⁵ + (lg x)⁴
   (Each part of this problem is worth 4 points.)

4. Give a big-Oh estimate for each of the following functions. For the function g(n) in your estimate "f(n) = O(g(n))" use a simple function g(n) close in size to f(n):
   (1) f(n) = (n³ + n²lg n)(lg n + 1) + (17 lg n + 19)(n³ + 2)
   (2) f(n) = (2ⁿ + n²)(n³ + 3ⁿ)
   (Each part of this problem is worth 4 points.)

5. If f₁(n) and f₂(n) are functions from the natural numbers to the positive real numbers and f₁(n) and f₂(n) are both Theta(g(n)), is f₁(n) - f₂(n) also Theta(g(n))? If your answer is yes, please prove it using the definition of Theta notation; if your answer is no, please give a counterexample. (4 points)

• Prove that if f(x) = a_nxⁿ + a_n-1x^n-1 + a₁x + a₀, where a_n, a_n-1, ..., a₁, a₀ are real numbers and a_n is not equal to 0, then f(x) = Theta(xⁿ). You may assume that x > 0.
  Please note that last week's challenge homework problem was to prove that this polynomial is Omega(xⁿ). If you submitted a solution for last week's challenge homework, you may appeal to that solution and submit a proof to show that f(x) above is O(xⁿ). (5 points)