Massachusetts Institute of Technology Handout 26 6.042J/18.062J: Mathematics for Computer Science October 9, 1998 Professors Nancy Lynch and Srini Devadas

Problems for Recitation 5

Problem 1. We begin with two large glasses. The first glass contains a pint of water, and the second contains a pint of wine. We pour 1/3 of a pint from the first glass into the second, stir up the wine/water mixture in the second glass, and then pour 1/3 of a pint of the mix back into the first glass. We now repeat this pouring back-and-forth process a total of n times.

(a) Describe a closed form formula for the amount of wine in the first glass after n back-and-forth pourings.

(b) What is the limit of the amount of wine in each glass as n approaches infinity?

Problem 2. (a) Give an example of functions f, g : ℕ → ℕ such that neither f = O(g) nor g = O(f). Prove it.

(b) Prove or give a counterexample: If f_{1}, f_{2}, … is a sequence of functions from ℕ to ℕ such that f_{i}(n) = O(1) for all i ≥ 1, then

∑_{i=1}^{n} f_{i}(n) = O(2^{n}).

Problem 3. (a) Show that the Master Theorem does not apply to

S(m) = S(m/2) + (log m)^{2}.

(b) Find a Θ() bound for S anyway.

(c) Find a Θ() bound for

T (n) = T (\sqrt{n}) + (lg lg n)^{2}.

The base condition is T (2) = 1.