MCS-177 Homework 3, Spring 2003

Due: March 12, 2003

• Do exercise 4.11 on pages 99-100.

• Exercise 4.x1: Where possible, fill in the blanks in the following statements with positive real numbers so as to make the statement true. Where impossible, put a question mark in the blank or blanks that you cannot truthfully fill in. (If it is possible to fill in one blank but not the other, fill in the one you can with a positive real number, the other with a question mark.)
  1. n is big Theta of 3n because for any n, ___ × 3n <= n <= ___ × 3n
  2. n³ + n is big Theta of n³ because for any n >= 1, ___ × n³ <= n³ + n <= ___ × n³
  3. n³ + n is big Theta of n because for any n >= 1, ___ × n <= n³ + n <= ___ × n
  4. n^1/2 is big Theta of n because for any n >= 0, ___ × n <= n^1/2 <= ___ × n
  5. n^1/2 is big Theta of n because for any n >= 1, ___ × n <= n^1/2 <= ___ × n

• Do exercise 4.13 on page 101. Be sure to give your answer in as simple a form as is possible.

• Do exercise 4.20 on pages 105-106.