Homework 2 - D Term 2008

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 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**(8 Points)**1 century

1 hour 1 week 1 year 1 century 1000n ^{3}n ^{4}n ^{2}log n3 ^{n}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(n^{k}).**(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)**3n ^{2}+ 10n + 8n ^{2}2. **(7 points)**2 ^{n}2 ^{(n+7)}3. **(7 points)**n(log(n)) ^{2}n ^{3}4. **(7 points)**3 ^{n}2 ^{n}5. **(7 points)**n ^{(1/2)}(=sqrt(n))n 6. **(3 points)**(2n) ^{log2(2n)}n ^{log2(n)}**(15 Points) Problem 4**Let k be a fixed constant, and let f_{1}, f_{2}, ..., f_{k}be functions such that f_{i}= O(f_{i+1}) for all i, 1 ≤ i < k. Prove that f_{1}+ f_{2}+ ... + f_{k}= Θ(f_{k}).