MatemathicsForComputerScientists
339 pág.

MatemathicsForComputerScientists


DisciplinaFundamentos de Algoritmos para Computação125 materiais621 seguidores
Pré-visualização50 páginas
case, k = 2, a1 = 2, a2 = 8/9, b1 = 1/2, b2 = 3/4, and g(x) = x2.
12.4.1 Solving Divide and Conquer Recurrences
A few years ago, two guys in Beirut named Akra and Bazzi discovered an elegant way to
solve all divide-and-conquer recurrences.
Theorem 76 (Akra-Bazzi, weak form). Suppose that:
T (x) =
\uf8f1\uf8f4\uf8f2\uf8f4\uf8f3
is defined for 0 \u2264 x \u2264 x0
k\u2211
i=1
aiT (bix) + g(x) for x > x0
where:
\u2022 a1, . . . , ak are positive constants
\u2022 b1, . . . , bk are constants between 0 and 1
\u2022 x0 is \u201clarge enough\u201d in a technical sense we leave unspecified
\u2022 |g\u2032(x)| = O(xc) for some c \u2208 N
Then:
T (x) = \u398
(
xp
(
1 +
\u222b x
1
g(u)
up+1
du
))
where p satisfies the equation
\u2211k
i=1 aib
p
i = 1.
We won\u2019t prove this here, but let\u2019s apply the theorem to solve the nasty recurrence
from above:
T (x) = 2T (x/2) + 8/9T (3x/4) + x2
The first step is to find p, which is defined by the equation:
2
(
1
2
)p
+
8
9
(
3
4
)p
= 1
Equations of this form don\u2019t always have closed-form solutions. But, in this case, the
solution is simple: p = 2. Next, we have to check that g\u2032(x) does not grow too fast:
|g\u2032(x)| = |2x| = O(x)
Recurrences I 157
Finally, we can compute the solution to the recurrence by integrating:
T (x) = \u398
(
x2
(
1 +
\u222b x
1
u2
u3
du
))
= \u398
(
x2 (1 + log x)
)
= \u398(x2 log x)
The Akra-Bazzi method an be frustrating, because you do a lot of inexplicable inter-
mediate calculations and then the answer just pops out of an integral. However, it goes
through divide-and-conquer recurrences like a Weed Wacker.
Let\u2019s try one more example. Suppose that the following recurrence holds for all suffi-
ciently large x:
T (x) = T (x/3) + T (x/4) + x
Here k = 2, a1 = 1, a2 = 1, b1 = 1/3, b2 = 1/4, and g(x) = x. Note that |g\u2032(x)| = 1 = O(1),
so the Akra-Bazzi theorem applies. The next job is to compute p, which is defined by the
equation: (
1
3
)p
+
(
1
4
)p
= 1
We\u2019re in trouble: there is no closed-form expression for p. But at least we can say p < 1,
and this turns out to be enough. Let\u2019s plow ahead and see why. The Akra-Bazzi theorem
says:
T (x) = \u398
(
xp
(
1 +
\u222b x
1
u
up+1
du
))
= \u398
(
xp
(
1 +
\u222b x
1
u\u2212p du
))
= \u398
(
xp
(
1 +
(
u1\u2212p
1\u2212 p
\u2223\u2223\u2223\u2223x
u=1
)))
= \u398
(
xp
(
1 +
x1\u2212p \u2212 1
1\u2212 p
))
= \u398
(
xp +
x
1\u2212 p \u2212
xp
1\u2212 p
)
= \u398(x)
In the last step, we use the fact that xp = o(x) since p < 1; in other words, the term
involving x dominates the terms involving xp, so we can ignore the latter. Overall, this
calculation show that we don\u2019t need to know the exact value of p because it cancels out!
In recitation we\u2019ll go over a slightly more general version of the Akra-Bazzi theorem.
This generalization says that small changes in the sizes of subproblems do not affect the
solution. This means that some apparent complications are actually irrelevant, which is
nice.
158 Recurrences I
Chapter 13
Recurrences II
13.1 Asymptotic Notation and Induction
We\u2019ve seen that asymptotic notation is quite useful, particularly in connection with re-
currences. And induction is our favorite proof technique. But mixing the two is risky
business; there is great potential for subtle errors and false conclusions!
False Claim 77. If
T (1) = 1
T (n) = 2T (n/2) + n
then T (n) = O(n).
This claim is false; the Akra-Bazzi theorem implies that the correct solution is T (n) =
\u398(n log n). But where does the following \u201cproof\u201d go astray?
Proof. The proof is by strong induction. Let P (n) be the proposition that T (n) = O(n).
Base case: P (1) is true because T (1) = 1 = O(1).
Inductive step: For n \u2265 2 assume P (1), P (2), . . . P (n\u2212 1) to prove P (n). We have:
T (n) = 2 · T (n/2) + n
= 2 ·O(n/2) + n
= O(n)
The first equation is the recurrence, the second uses the assumption P (n/2), and the third
is a simplification.
Where\u2019s the bug? The proof is already far off the mark in the second sentence, which
defines the induction hypothesis. The statement \u201cT (n) = O(n)\u201d is either true or false; its
160 Recurrences II
validity does not depend on a particular value of n. Thus, the very idea of trying to prove
that the statement holds for n = 0, 1, 2, . . . is wrong-headed.
The safe way to reason inductively about asymptotic phenomena is to work directly
with the definition of the notation. Let\u2019s try to prove the claim above in this way. Remember
that f(n) = O(n) means that there exist constants n0 and c > 0 such that |f(n)| \u2264 cn for
all n \u2265 n0. (Let\u2019s not worry about the absolute value for now.) If all goes well, the proof
attempt should fail in some blatantly obvious way, instead of in a subtle, hard-to-detect
way like the earlier argument. Since our perverse goal is to demonstrate that the proof
won\u2019t work for any constants n0 and c, we\u2019ll leave these as variables and assume only that
they\u2019re chosen so that the base case holds; that is, T (n0) \u2264 cn.
Proof Attempt. We use strong induction. Let P (n) be the proposition that T (n) \u2264 cn.
Base case: P (n0) is true, because T (n0) \u2264 cn.
Inductive step: For n > n0, assume that P (n0), . . . , P (n\u2212 1) are true in order to prove P (n).
We reason as follows:
T (n) = 2T (n/2) + n
\u2264 2c(n/2) + n
= cn+ n
= (c+ 1)n
6\u2264 cn
The first equation is the recurrence. Then we use induction and simplify until the argu-
ment collapses!
13.2 Linear Recurrences
Last lecture we saw how to solve Divide and Conquer recurrences. In this lecture, we\u2019ll
consider another family of recurrences, called \u201clinear recurrences\u201d, that also frequently
arise in computer science and other disciplines. We\u2019ll first see how to solve a specific
linear recurrence and then generalize our method to work for all linear recurrences.
13.2.1 Graduate Student Job Prospects
In a new academic field (say computer science), there are only so many faculty positions
available in all the universities of the world. Initially, there were not enough qualified
candidates, and many positions were unfilled. But, over time, new graduates are filling
the positions, making job prospects for later computer science students ever more bleak.
Worse, the increasing number of professors are able to train an increasing number of
graduate students, causing positions to fill ever more rapidly. Eventually, the universities
will be saturated; new computer science graduates will have no chance at an academic
Recurrences II 161
career. Our problem is to determine when the universities will stop hiring new computer
science faculty and, in particular, to answer the question, \u201cAre the 6.042 TAs doomed?\u201d
Here are the details of the problem.
\u2022 There are a total of N faculty positions available worldwide. This number never
changes due to budgetary constraints.
\u2022 Congress has passed a law forbidding forced retirement in universities, and no one
will retire voluntarily. (This is true and a problem!) In our analysis, therefore, once
a faculty position is filled, it never opens up again.
\u2022 Each year, every professor trains exactly 1 student who will go on to become a pro-
fessor the following year. The only exception is that first year professors do not
train students; they are too busy publishing, teaching, getting grants, and serving
on committees.
\u2022 In year 0, there are no computer science professors in the world. In year 1, the first
professor is hired.
13.2.2 Finding a Recurrence
Ideally, we could find a formula for the number of professors in the world in a given year.
Then we could determine the year in which all N faculty positions are filled. Let f(n) be
the number of professors during year n. To develop some intuition about the problem,
we can compute values of this function for small n by hand.
f(0) = 0 No CS professors; the dark ages.
f(1) = 1 1 new professor; too busy to train a student.
f(2)