MCS177 Homework 3, Spring 2003
Due: March 12, 2003
 Do exercise 4.11 on pages 99100.
 Exercise 4.x1:
Where possible, fill in the blanks in the following statements with
positive real numbers so as to make the statement true. Where
impossible, put a question mark in the blank or blanks that you cannot
truthfully fill in. (If it is possible to fill in one blank but not
the other, fill in the one you can with a positive real number, the
other with a question mark.)
 n is big Theta of 3n because for any
n, ___ × 3n <= n <= ___
× 3n

n^{3} + n
is big Theta of
n^{3}
because for any n >=
1,
___ ×
n^{3}
<=
n^{3} + n
<= ___ ×
n^{3}

n^{3} + n
is big Theta of
n
because for any n >=
1,
___ ×
n
<=
n^{3} + n
<= ___ ×
n

n^{1/2}
is big Theta of
n
because for any n >=
0,
___ ×
n
<=
n^{1/2}
<= ___ ×
n

n^{1/2}
is big Theta of
n
because for any n >=
1,
___ ×
n
<=
n^{1/2}
<= ___ ×
n
 Do exercise 4.13 on page 101. Be sure to give your answer in
as simple a form as is possible.
 Do exercise 4.20 on pages 105106.