# Problem Set 4 Solution

\$35.00 \$30.80

Category:

## Description

Total 100 points.

Problem 1. (5 points) Let x be a real number and n an integer. Show that

rxs  n if and only if x ¤ n x 1:

[Hint: Use the de nition for rxs  n given as the second fact among the four facts in slide #39 in the lecture slides on Sets and Functions. What you are proving here is the last fact in the same slide.]

Problem 2. (15 points) Let n be a positive integer. Show that if n is a perfect square, then

Problem 3. (10 points) Let f1; f2; f3 be functions from the set N of natural numbers to the set R of real numbers. Suppose that f1  Opf2q and f2  Opf3q. Is it possible that

Problem 4. (10 pts  3 = 30 points) Determine whether each of the following statements is true or false. In each case, answer true or false, and justify your answer (by giving a direct proof if it is true, or a proof by contradiction if it is false; always use the de nition involving the absolute values, as given in class).

Problem 5. (10 points) Let k be a  xed positive integer. Show that

1k 2k       nk  Opnk  1q

holds.

Problem 7. (5 pts  3 = 15 points) Suppose that you have two algorithms A and B that solve the same problem. Algorithm A has worst case running time TApnq  2n2   2n 1 and Algorithm B has worst case running time TBpnq  n2 n   1.

1. Show that both TApnqand TBpnq are in Opn2q.
2. Show that TApnq2n2   Opnq and TBpnq  n2   Opnq.

1. Explain which algorithm is preferable.

Checklist:

• Did you type in your name and UIN?

• Did you disclose all resources that you have used?

(This includes all people, books, websites, etc. that you have consulted.)

• Did you electronically sign that you followed the Aggie Honor Code?

• Did you solve all problems?

• Did you submit both of the .tex and .pdf les of your homework to the correct link on eCampus?

5