### CS2223 Algorithms Homework 2 - D Term 2009

#### PROF. CAROLINA RUIZ

Due Date: March 31, 2009 at 1:00 PM
See course policy regarding late homework submissions

• Homework Instructions:

• 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 (you can assume that 1 year = 365 days)
• (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 518n n5 log10(n) 4n n(1/3) (= cubic root of n)

2. (40 Points) Problem 2. 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, that is, provide a formal, mathematical proof using either the definitions of O, Ω, and Θ; or the theorems stated in class or in the textbook. (It is not enough just to say for instance that "exponential grows faster than polynomial".)
 f(n) g(n) 1.(8 points) n2 * log(n) n2 2.(8 points) n2 * log(n) n3 3.(8 points) 3n 3(n+3) 4.(8 points) 33n 3n 5.(8 points) n(1/2) (=sqrt(n)) log(n)

3. (28 Points) Problem 3. Construct a formal mathematical proof of each of the following two properties using the definitions of O, Ω, and Θ.

• (14 points) Transpose symmetry of O and Ω: f(n) is O(g(n)) if and only if g(n) is Ω(f(n)).

• (14 points) Symmetry of Θ: f(n) is Θ(g(n)) if and only if g(n) is Θ(f(n)).