### CS2223 Algorithms Homework 2 - D Term 2008

#### PROF. CAROLINA RUIZ

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.
• See the course webpage for the late homework submission policy.

• Homework Problems:

1. (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))

2. (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).

3. (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)

4. (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).