MCS177 Homework 3, Spring 2001
Due: March 7, 2001

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^{2} if there are two positive multiples
of n^{2} that the given function always stays
between, except perhaps for some finite number of exceptions.
For example it might stay between 1/4 n^{2} and
2 n^{2} (as on page 81), or between
5 n^{2} and 9 n^{2}.
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.

n^{3} is big theta of n^{2}

n is big theta of n^{2}

3n^{2} is big theta of n^{2}

Do exercise 4.1 on page 81.
Instructor: Max Hailperin