MCS-177 Homework 3, Fall 1999

Due: October 8, 1999

1. In this problem, assume that n is a variable ranging over the nonnegative integers. As described on page 81, we say that a function of n is big theta of n² if there are two positive multiples of n² that the given function always stays between, except perhaps for some finite number of exceptions. For example it might stay between 1/4 n² and 2 n² (as on page 81), or between 5 n² and 9 n². Using this definition, decide whether each of the following claims is true or false, and write a brief justification of your answer in each case.
   1. n³ is big theta of n²
   2. n is big theta of n²
   3. 3n² is big theta of n²

2. Do exercise 4.1 on page 81.

Instructor: Max Hailperin