Due Date: March 25, 2008 at 1:00 PM
See course policy regarding late homework submissions
- Homework Instructions:
- Read Chapter 2 of the textbook in detail.
- See Useful logarithm and exponential facts.
- This is an individual homework. No collaboration is allowed.
- Submit a hardcopy of your written homework solutions by the
beginning of class (i.e., 1:00 pm) the day the homework is due.
- Remember to show your work and explain your answers.
Correct answers without complete explanations won't receive full credit.
Incorrect answers with explanations may receive partial credit.
- See the course webpage for
the late homework submission policy.
- Homework Problems:
- (32 Points) Problem 1.
Suppose you have algorithms with the running times listed below.
Assume these are the exact number of operations performed as a
function of the input size n.
Suppose you have a computer that can perform 1010
operations per second, and you need to compute results in at most
- (8 Points) 1 hour
- (8 Points) 1 week
- (8 Points) 1 year
- (8 Points) 1 century
For each of the algorithms, what is the largest input size n
for which you would be able to get the result within the given
time limit?
That is, your solutions to this exercise should contain a table like
the one below together with explanations for each of the values you
provide in your table.
| | 1 hour | 1 week | 1 year | 1 century
|
| 1000n3
| | | |
|
| n4
| | | |
|
| n2 log n
| | | |
|
| 3n
| | | |
|
| n(1/2) (= sqrt(n))
| | | |
|
- (15 Points) Problem 2
Assume that k is a fixed constant. Prove that
if f(n) = O(n) then (f(n))k is O(nk).
- (38 Points) Problem 3
In each of the following cases, determine whether
f(n) = O(g(n)), or
f(n) = Ω(g(n)), or
both (i.e., f(n) = Θ(g(n))), or
none of the above.
Prove your answers decisively.
| | f(n) | g(n)
|
| 1.(7 points) | 3n2 + 10n + 8 | n2
|
| 2.(7 points) | 2n | 2(n+7)
|
| 3.(7 points) | n(log(n))2 | n3
|
| 4.(7 points) | 3n | 2n
|
| 5.(7 points) | n(1/2) (=sqrt(n)) | n
|
| 6.(3 points) | (2n)log2(2n) | nlog2(n)
|
- (15 Points) Problem 4
Let k be a fixed constant, and let
f1,
f2, ...,
fk
be functions such that
fi = O(fi+1) for all i, 1 ≤ i < k.
Prove that
f1 +
f2 + ... +
fk
= Θ(fk).