MCS-177 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 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.
n3 is big theta of n2
n is big theta of n2
3n2 is big theta of n2
Do exercise 4.1 on page 81.
Instructor: Max Hailperin