MCS-177 Homework 3, Fall 1999
Due: October 8, 1999
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
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