Massachusetts Institute of Technology Handout 32 6.042J/18.062J: Mathematics for Computer Science October 20, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 5 Solutions

Read sections 1.7, 1.8, 5.1, 5.2, and 5.3 in Rosen.

Problem 1. (15 points) In 1997 there was a breakthrough on a long-standing problem in computer science called The Traveling Salesman Problem. The idea is that there is a salesman who wants to visit n cities scattered around the country. The problem is to determine the order in which he should visit the cities so as to minimize the total distance that he travels, assuming that he can go in a straight line between any two cities. Surprisingly, this problem is very difficult when the number of cities n is large.

The breakthrough was an algorithm that efficiently computes a nearly-optimal solution, a route for the salesman that has length at most 10% greater than the shortest possible route. The running time of the algorithm is described in the orginal publication as “nearly linear” in the number of cities. More precisely, the algorithm requires about n ln^{400} n steps.

(a) Prove that n ln^{400} n is o(n^{1.1}). This shows that the algorithm truly is “nearly linear” in an asymptotic sense. You may make use of L’Hopital’s rule:

If lim_{n→∞} f(n) = ∞ and lim_{n→∞} g(n) = ∞, then lim_{n→∞} \frac{f(n)}{g(n)} = lim_{n→∞} \frac{f′(n)}{g′(n)}.

Proof. We will first use L’Hopital’s Rule to prove that the ratio of the two running times tends to zero.

lim_{n→∞} \frac{n ln^{400} n}{n^{1.1}} = lim_{n→∞} \frac{ln^{400} n}{n^{0.1}}
= ( lim_{n→∞} \frac{ln n}{n^{1/4000}} )^{400}
= ( lim_{n→∞} \frac{1/n}{\frac{1}{4000}n^{−3999/4000}} )^{400}
= ( lim_{n→∞} \frac{4000}{n^{1/4000}} )^{400}
= 0^{400}

The first step is simplification. The second step uses the fact that the limit of a product is the product of the limits. L’Hopital’s rule is applied in the third step, and the remaining steps are simplifications.

The definition of a limit implies that for all c > 0, there exists an n_{0} such that n ln^{400} n/n^{1.1} < c for all n ≥ n_{0}. Rewriting this inequality as n ln^{400} n < cn^{1.1}, we establish that n ln^{400} n = o(n^{1.1}) by the definition of o.

(b) Find a specific value of n such that n^{1.1} is actually greater than n ln^{400} n.

We forgot to rule out small values of n. Thus, for example, n = 1 is an acceptable answer worth full credit. However, you are a SUPERIOR HUMAN BEING if you followed the intent of the question and identified an n such that the inequality holds for that value and for all larger values. Suppose that we choose n = e^{50000}, a number with more than twenty-one thousand digits. Then n^{1.1} is equal to e^{55000}, and n ln^{400} n is equal to e^{50000}·50000^{400} = e^{50000+400 ln 50000} ≈ e^{54328}, which is a little smaller. Note that setting n equal to e^{40000}— a paltry seventeen thousand digit number— would not suffice. Asymptotic notation can be misleading!

Problem 2. (10 points) Order the functions in each set below so that each function is either O or Θ of the next function. Indicate whether the stronger Θ relationship holds in each case. No proofs are required.

Example. n^{2}, n, n^{3}/(n + 1), 3n^{2}

n = O(n^{2})
n^{2} = Θ(3n^{2})
3n^{2} = Θ(n^{3}/(n + 1))

(a) ln n, ln \sqrt{n}, \sqrt{ln n}, n^{1/n}

n^{1/n} = O(\sqrt{ln n})
\sqrt{ln n} = O(ln \sqrt{n})
ln \sqrt{n} = Θ(ln n)

(b) (\sqrt{n})^{2 ln ln n}, n, n ln n, ln n^{ln n}, ln n!

The notation ln n^{ln n} was ambiguous, and so two solutions are acceptable.

n = O(n ln n)
n ln n = Θ(ln n!)
ln n! = O((ln n)^{ln n})
(ln n)^{ln n} = Θ((\sqrt{n})^{2 ln ln n})

Alternatively,

ln(n^{ln n}) = O(n)
n = O(n ln n)
n ln n = Θ(ln n!)
ln n! = O((\sqrt{n})^{2 ln ln n})

(c) n!, n^{n}, (n/3)^{n}, n^{n+ln ln n}, e^{n ln ln n}

e^{n ln ln n} = O((n/3)^{n})
(n/3)^{n} = O(n!)
n! = O(n^{n})
n^{n} = O(n^{n+ln ln n})

The hardest relation here was probably (n/3)^{n} = O(n!). The integral method gives the following.

ln n! ≥ ∫_{1}^{n} ln u du
= n ln n − n + 1
n! ≥ e^{n ln n−n+1}
≥ (\frac{n}{e})^{n}

The ratio (n/3)^{n} divided by (n/e)^{n} is equal to (e/3)^{n}, which tends to 0 as n goes to infinity. This implies an O-relationship rather than a Θ-relationship.

Problem 3. (10 points) Suppose that n ovals are drawn in a plane so that every pair of ovals intersects at either 0 or 2 points. Let x_{n} be the maximum number of regions that can be formed by such a configuration of ovals. We can express x_{n} using the recurrence below.

x_{1} = 2
x_{n+1} = x_{n} + 2n

The region outside of any oval “counts”; for example, one oval defines two regions, because the oval has an inside region and an outside region.

(a) Solve this recurrence using the plug and chug method.

First, we repeatedly apply the recurrence equation.

x_{n} = x_{n−1} + 2(n − 1)
= x_{n−2} + 2(n − 2) + 2(n − 1)
= x_{n−3} + 2(n − 3) + 2(n − 2) + 2(n − 1)

We can now guess a general form and check it by applying the recurrence equation one more time.

x_{n} = x_{n−i} + 2(n − i) + … + 2(n − 2) + 2(n − 1)
x_{n} = x_{n−i−1} + 2(n − i − 1) + 2(n − i) + … + 2(n − 2) + 2(n − 1)
= x_{n−(i+1)} + 2(n − (i + 1)) + 2(n − i) + … + 2(n − 2) + 2(n − 1)

Setting i = n − 1, gives an expression for x_{n}.

x_{n} = x_{n−i} + 2(n − i) + … + 2(n − 2) + 2(n − 1)
= x_{1} + 2 + 4 + … + 2(n − 2) + 2(n − 1)
= 2 + 2 + 4 + … + 2(n − 2) + 2(n − 1)
= 2 + 2 ∑_{j=1}^{n−1} j

Now we get the closed form x_{n} = n(n − 1) + 2 from the formula for the sum of an arithmetic series.

(b) Describe how to arrange n ovals so as to form x_{n} regions. No proof of correctness is required.

Make all the ovals circles of the same size. Place the second circle slightly right of the first, the third slightly right of the second, and so forth.

Problem 4. (10 points) Consider the following recurrence.

y_{0} = 1
y_{n} = ∑_{i=1}^{n} y_{n−i} · 2^{i}

(a) Guess the solution to the recurrence.

First, we compute the first few terms to form the basis for a guess.

y_{0} = 1
y_{1} = 2 · y_{0} = 2 · 1 = 2
y_{2} = 2 · y_{1} + 4 · y_{0} = 2 · 2 + 4 · 1 = 8
y_{3} = 2 · y_{2} + 4 · y_{1} + 8 · y_{0} = 2 · 8 + 4 · 2 + 8 · 1 = 32
y_{4} = 2 · y_{3} + 4 · y_{2} + 8 · y_{1} + 16 · y_{0} = 2 · 32 + 4 · 8 + 8 · 2 + 16 · 1 = 128

The above calculation suggests the following claim.

Claim. The solution to the recurrence is y_{0} = 1 and y_{n} = 2^{2n−1} for n ≥ 1.

(b) Prove your guess correct using strong induction.

Proof. The proof is by strong induction. Let P (n) be the proposition that y_{0} = 1 and y_{n} = 2^{2n−1} for n ≥ 1. In the base case, P (0) holds trivially. In the inductive step, assume P (0), …, P (n) to prove P (n + 1). By the definition of y_{n+1}, we have:

y_{n+1} = ∑_{i=1}^{n+1} y_{n+1−i} · 2^{i}

= y_{0} · 2^{n+1} + ∑_{i=1}^{n} y_{n+1−i} · 2^{i}

= 1 · 2^{n+1} + ∑_{i=1}^{n} 2^{2(n+1−i)−1} · 2^{i}

= 2^{n+1} + 2^{2n+1} · ∑_{i=1}^{n} \frac{1}{2^{i}}

= 2^{n+1} + 2^{2n+1} · (1 − \frac{1}{2^{n}} )
= 2^{2(n+1)−1}

In the second step, we split out the special term of the summation that contains y_{0}. The third step uses the induction hypotheses, and in the fourth step we pull a constant out of the summation. The fifth equation follows from the formula for the sum of a geometric series. The last step is simplication.

This shows that P (0), …, P (n) imply P (n + 1), and the claim is proved by strong induction.

Problem 5. (10 points) The following recurrence was invented by a late Italian renaissance scholar named Giardi Invertabinacci, who earned a certain repute in his age for mocking profound ideas, poetry, sculpture, and even architecture by constructing upside-down or backward replicas of the orignal. His scaled model of the famed Tower of Pisa still stands– upside down, but not leaning– outside Palermo. His one venture into mathematics was a recurrence relation, recorded in a letter to a contemporary mathematician and reproduced below in modern notation.^{1}

x_{1} = 1
x_{2} = 1
x_{n+1} = \frac{x_{n}x_{n−1}}{x_{n} + x_{n−1}}

(a) Guess the solution to the recurrence. Your solution may be expressed in terms of Fibonacci numbers.

We compute the first few terms to form the basis for a guess at the general solution.

x_{1} = 1
x_{2} = 1
x_{3} = \frac{x_{2}x_{1}}{x_{2} + x_{1}} = \frac{1 · 1}{1 + 1} = \frac{1}{2}
x_{4} = \frac{x_{3}x_{2}}{x_{3} + x_{2}} = \frac{\frac{1}{2} · 1}{\frac{1}{2} + 1} = \frac{1}{3}
x_{5} = \frac{x_{4}x_{3}}{x_{4} + x_{3}} = \frac{\frac{1}{3} · \frac{1}{2}}{\frac{1}{3} + \frac{1}{2}} = \frac{1}{5}
x_{5} = \frac{x_{5}x_{4}}{x_{5} + x_{4}} = \frac{\frac{1}{5} · \frac{1}{3}}{\frac{1}{5} + \frac{1}{3}} = \frac{1}{8}

1Okay, your TA just made all this up. But good story, eh?

Guess. The solution to the recurrence is x_{n} = 1/F_{n}.

(b) Use strong induction to prove your guess correct.

Proof. The proof is by induction. Let P (n) be the proposition that x_{n} = 1/F_{n}. In the base cases, P (1) is true because x_{1} = 1 = 1/F_{1}, and P (2) is true because x_{2} = 1 = 1/F_{2}. In the inductive step, for n ≥ 2 assume P (1), …, P (n) to prove P (n + 1). From the defintion of x_{n+1}, we reason as follows:

x_{n+1} = \frac{x_{n}x_{n−1}}{x_{n} + x_{n−1}}
= \frac{\frac{1}{F_{n}} \frac{1}{F_{n−1}}}{\frac{1}{F_{n}} + \frac{1}{F_{n−1}}}
= \frac{1}{F_{n−1} + F_{n}}
= \frac{1}{F_{n+1}}

The second step uses the induction hypotheses, the third step is simplification, and final step uses the Fibonacci recurrence.

Problem 6. (20 points) Recently, Theory Pig found a small piece of blue crayon behind the filing cabinet in Professor Lynch’s office. Theory Pig was delighted to find that with this wondrous new toy he could draw pretty blue rectangles with a width of w centimeters and a height of ln w centimeters for any w > 1 that he took a fancy to.

w  ln w

Our pal proudly presented this remarkable discovery to 6.042 TA Rodrigo Leroux. Rodrigo was unimpressed: “Yeah, but what if I want a rectangle with an area of n square centimeters?

Then what should be the width w?” Fidgeting nervously with his crayon, Theory Pig replied that he believed the width should be Θ(n/ ln n) asymptotically, but that unfortunately he could not rigorously prove this fact. Rodrigo replied, “If you can’t play with your toys properly, then they’ll be taken away!” And then he confiscated Theory Pig’s crayon!

Return joy to our little pal’s world by supplying a proof of his claim.

Let f(w) = w ln w. Then a rectangle with width w has area f(w). Consequently, a rectangle with area n should have width f^{−1}(n). We can now formalize the problem as follows.

Claim. If f(w) = w ln w, then f^{−1}(n) = Θ(n/ ln n).

Proof. We must prove that there exists an n_{0} and constants c_{1}, c_{2} > 0 such that for all n > n_{0}

c_{1} · \frac{n}{ln n} ≥ f^{−1}(n) ≥ c_{2} · \frac{n}{ln n}.

Since f is an increasing function, the above inequalities hold if and only if

f (c_{1} · \frac{n}{ln n}) ≥ f(f^{−1}(n)) ≥ f (c_{2} · \frac{n}{ln n}) .

Suppose that we choose c_{1} = e and c_{2} = 1. Then the inqualities can be rewritten as follows:

e · \frac{n}{ln n} · ln (e · \frac{n}{ln n}) ≥ n ≥ \frac{n}{ln n} · ln (\frac{n}{ln n})

n · (e + \frac{e}{ln n} − \frac{e ln ln n}{ln n}) ≥ n ≥ n · (1 − \frac{ln ln n}{ln n})

In the expression on the left, the e ln ln n/ ln n term is o(1), and so the expression in parentheses is greater than 1 for all sufficiently large n. In the expression on the right, the ln ln n/ ln n term is positive for all n > e, and so the expression is parentheses is less than 1 for all sufficiently large n. Therefore, there exists an n_{0} such that both inequalities hold for all n > n_{0} as desired.

Problem 7. (10 points) We have devised a new version of MergeSort, which we call MergeSortX19, for the intellectually challenged inhabitants of planet Xoros 19.

Here is how the new algorithm works. The input is a list of n distinct numbers. If the list contains a single number, then there is nothing to do. If the list contains two numbers, then we sort them with a single comparison. If the list contains more than two numbers, then we perform the following sequence of steps.

• We make a list containing the first \frac{2}{3}n numbers and sort it recursively.

• We make a list containing the last \frac{2}{3}n numbers and sort it recursively.

• We make a list containing the first \frac{1}{3}n numbers and the last \frac{1}{3}n numbers and sort it recursively.

• We merge the first and second lists, throwing out duplicates.

• We merge this combined list with the third list, again throwing out duplicates.

The final, merged list is the output. We consider this algorithm ideal for the slow-witted creatures of Xoros 19, because multiple copies of each number are maintained. Therefore, even if the sorter occasionally forgets about a number, the algorithm can still output a complete, sorted list.

(a) Write a recurrence for the maximum number of comparisons needed to sort a list of n numbers using MergeSortX19. Assume that merging a list with l_{1} numbers and a list with l_{2} numbers and throwing out duplicates requires at most 2(l_{1} +l_{2}) comparisons.

T (1) = 0
T (2) = 1
T (n) = 3T (\frac{2}{3}n) + 2 (\frac{2}{3}n + \frac{2}{3}n) + 2 (n + \frac{2}{3}n)
= 3T (\frac{2}{3}n) + 6n

(b) Give a Θ bound on the maximum number of comparisons used by MergeSortX19 to sort a list of n numbers.

We can apply the Akra-Bazzi method. First, we find p as shown below.

3 · (\frac{2}{3})^{p} = 1
ln 3 − p ln \frac{3}{2} = 0
p = \frac{ln 3}{ln \frac{3}{2}}

Now the Θ bound on the maximum number of comparisons follows from an integration.

x_{n} = Θ (n^{p} · (1 + ∫_{1}^{n} \frac{6u}{u^{1+p}} du))
= Θ (n^{p})
= Θ (n^{2.7095...})

Problem 8. (15 points) Use the Akra-Bazzi method to find a Θ bound on the solution to each of the following recurrences.

(a) T (n) = 4T (⌊\frac{n}{3}⌋) + n^{2}

4 · (1/3)^{p} = 1 ⇒ p = ln_{3} 4
T (n) = Θ (n^{p} · (1 + ∫_{1}^{n} \frac{u^{2}}{u^{p+1}} du))
= Θ(n^{2})

(b) T (n) = T (⌊\frac{3n}{5}⌋) + T (⌊\frac{4n}{5}⌋) + n^{2}

(3/5)^{p} + (4/5)^{p} = 1 ⇒ p = 2
T (n) = Θ (n^{2} · (1 + ∫_{1}^{n} \frac{u^{2}}{u^{2+1}} du))
= Θ(n^{2} ln n)

(c) T (n) = T (⌊\frac{n}{3}⌋) + 2T (⌊\frac{n}{4}⌋) + n\sqrt{n}

(1/3)^{p} + 2(1/4)^{p} = 1 ⇒ p < 1
T (n) = Θ (n^{p} · (1 + ∫_{1}^{n} \frac{u^{3/2}}{u^{p+1}} du))
= Θ (n^{p} · (1 + ∫_{1}^{n} u^{1/2−p} du))
= Θ(n\sqrt{n})