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 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.
    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