Homework 2 - D Term 2009

See course policy regarding late homework submissions

**Homework Instructions:**- Read Chapter 2 of the textbook in detail.
- See Useful facts about logarithms and exponentials.
- See Useful theorems for comparing the rates of growth of functions.
- 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 10^{10}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

1 hour 1 week 1 year 1 century 518n n ^{5}log _{10}(n)4 ^{n}n ^{(1/3)}(= cubic root of n)**(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)**n ^{2}* log(n)n ^{2}2. **(8 points)**n ^{2}* log(n)n ^{3}3. **(8 points)**3 ^{n}3 ^{(n+3)}4. **(8 points)**3 ^{3n}3 ^{n}5. **(8 points)**n ^{(1/2)}(=sqrt(n))log(n) **(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)).