This monograph collects some fundamental mathematical techniques that are required for the analysis of algorithms. It builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in the precise analysis of algorithms, emphasizing the more difficult notions. The authors cover recurrence relations, operator methods, and asymptotic analysis in a format that is concise enough for easy reference yet detailed enough for those with little background with the material.

> 0 m+l Zkm-- (4.14) e4 )m-1 t[1'1% 4 I-... + ( - 1 --m + O(e'n+x) e2 e3 In(1 + e) = e - ~ -t 3 n 1 t- O(n -4) mn m- 1 12 (4.17) + o(nm-2), m > 1 ( B i ( x ) and Bi are the Bernoulli polynomials and numbers, see page 59.) " E k--no 1 k lnk lnlnk " " " - O(1), > 0 (ln (') k) i+~ The last equation represents the turning point for sums. When e = 0 the sums will diverge. For example, the sums ~k' 1 ~ 1 klnk' and ~ 1 klnklnlnk are all unbounded. There are several ways to

km (4"22) where each of the k's is distinct. Each term like (4.22) corresponds to a partition of n into distinct integers kl, k2,. 9 kin. Suppose we are to construct a polynomial of size n by multiplying polynomials of sizes k l , k 2 , . . . , kin. (We assume that these small polynomials and the large polynomial are all monic. Other leading coefficients do not affect the results that follow.) There are pk~ polynomials of degree kl. Of these pk~/k 1 are irreducible, by our assumption. Treating

is f I" N I tdt/lnt=] du/lnu= L(N) Jv~ ,12 SOLUTIONS TO FINAL EXAM I 97 [so, curiously, ~p<_v~ P ~ ~p<_N 1], which integrates by parts into the well known asymptotic form N/In N + N/(ln N) 2 + 2! IV/(InN) 3+ 9-. + 998! N/(lnN) 999 + O(N/(log N)l~176176 (b) The unusual numbers n < N whose largest prime factor is a given prime p > v/N are the [N/pJ numbers p, 2p,..., IN/pip. So there are ~p>v~LN/pJ unusual numbers of type (b). This equals f~N[N/tJ &r(t) = f~N [N/tJ dL(t) + f~N [N/tJ

what happens." Running to his interactive workstation, he hastily prepared a file containing a description of his new data structure, which he chose to call Late Binding Trees (LBTs); and then he ate breakfast. Unfortunately there is not room here to describe the subsequent events in Quick's life. The story about his fateful encounters with the Chuvstvenni sisters in Gstaad, who vowed to stop at nothing until they had learned his secret, will probably never be told. Let us rather turn our

when n = k, without affecting the orthogonal character of the equation. The last equation, (1.25), has an extremely useful combinatorial significance. Suppose we have a large collection of random events. Let bn be the probability that exactly n events occur, and let an be the sum of the probability of n simultaneous events taken over all selections of n events. Roughly speaking an can be viewed as a sloppy way of computing the probability that exactly n events occur since it makes no allowance