MCS-177 Homework 3, Spring 2001

Due: March 7, 2001

  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 n2 if there are two positive multiples of n2 that the given function always stays between, except perhaps for some finite number of exceptions. For example it might stay between 1/4 n2 and 2 n2 (as on page 81), or between 5 n2 and 9 n2. 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. To justify your answer, if the claim is true, you can state what the two positive multiples could be. If the claim is false, you need to explain which of the two multiples (the upper bound and the lower bound) is impossible to find, and why. Of course, it could be that neither bound can be found.
    1. n3 is big theta of n2
    2. n is big theta of n2
    3. 3n2 is big theta of n2

  2. Do exercise 4.1 on page 81.

Instructor: Max Hailperin