22 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples which is justified by approximation by an integral,as described in the next section.(For any specific k an exact formula can be proved by induction.)Compare this kind of series carefully with"geometric series,"which follow. Powers of 2:This is a frequently occurring case of a geometric series. 2=2*+-1 (1.8) i=0 How to remember it:Think of each term 2'as a 1-bit in a binary number;then: 2=11..1 1=0 There arek+1 1-bits.If I is added to this number the result is 100..0=2+1 (This result can also be obtained by using the following formula for the geometric series.) Geometric Series: (1.9) To verify this,divide out the right-hand side.As a special case,with r=,we have =2-21 (1.10) =0 A geometric series is distinguished by having a constant in the base and a variable in the exponent.A polynomial series has a variable in the base and a constant exponent.The behaviors are quite different. Harmonic Series: ≈ln()+y, where y≈.577. (1.11) i=I The sum is called the nth Harmonic number.The constant y is called Euler's constant.See also Example 1.7. Arithmetic-Geometric Series:In the next sum,the i term would give us an arithmetic series and the 2'term would give us a geometric series,hence the name. ∑2=k-1)2*+1+2. (1.12)
1.3 Mathematical Background 23 The derivation is an example of"summation by parts,"which is analogous to"integration by parts."The sum is rearranged into a difference of two sums that cancel except for their first and last terms,minus a third sum of a simpler form: ∑i2=∑2+-2y = i=1 k-1 =∑i2+-∑+1)2+1 i=l i=0 k-1 =∑i2+1-∑i2*1-∑2+ i=1 i=0 i=0 =k2+1-0-(2*+1-2)=(k-1)2+1+2. Fibonacci Numbers: The Fibonacci sequence is defined recursively as: Fw=Fn-1十Fa-2 forh≥2， (1.13) F0=0,F=1. Although this is not a summation,the series occurs frequently in analysis of algorithms. Monotonic and Convex Functions Sometimes very general properties are enough for us to draw some useful conclusions about the behavior of functions.Two such properties are monotonicity and convexiry. Throughout the discussion of monotonicity and convexity in this section,we assume some interval a<x <oo is understood,where a is usually 0,but might be I if logs are involved. All points mentioned are in this interval,and f is defined in this interval.The domain may be either reals or integers. Definition 1.7 Monotonic and antimonotonic functions A function f(x)is said to be monotonic,or nondecreasing,if x s y always implies that f(x)s f(y).A function f(x)is antimonotonic,or nonincreasing,if-f(x)is monotonic. Examples of familiar monotonic functions are x,x2 for x20,log(x)for x>0,and e*.Less familiar monotonic functions are Lx]and [x],showing that monotonic functions need not be continuous.An antimonotonic example is 1/x for x >0. Definition 1.8 Linear interpolation function The linear interpolation of a given function f(x)between two points u and v,u<v,is the function defined by
24 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples fx (a)Linear interpolation (b)Extension of f(n)to f*(x) Figure 1.3 Iilustratious for convexity discussion:The function f is different in parts (a)and (b).In part (b),f(x)is convex. Ly4nx)=包-xf四+x-)f间 (v-4) =fa)+c-f0-f@=jo-e-xf)-10,1.14 v-u v-4 that is,the straight-line segment joining f(u)and f(v)(see Figure 1.3a). Definition 1.9 Convex functions A function f()is saidto be convex if for all uv,f(x)in the interval (u.v). Informally,f(x)is convex if it never curves downward. Thus functions like x,x2,1/x,and e*are convex.The function in Figure 1.3(b)is convex (but not monotonic),whether interpreted on the reals or just on the integers;the function in Figure 1.3(a)is monotonic,but not convex.Also,log(x)and x are not convex. What about x log(x)?The following lemmas develop some practical tests for convexity. It is easy to see (and possible to prove)that a discontinuous function cannot be convex. Lemma 1.3 states that it is sufficient to consider equally spaced points to test for convexity, which simplifies things considerably.The proof is Exercise 1.16. Lemma 1.3 1.Let f(x)be a continuous function defined on the reals.Then f(x)is convex if and only if,for any points x,y, f(a+y)≤(fx)+f0y). In woids,f evaluated at the midpoint between x and y lies on or below the midpoint of the linear interpolation of f between x and y.Note that the midpoint of the linear interpolation is just the average of f(x)and f(y)
1.3 Mathematical Background 25 2.A function f(n)defined on integers is convex if and only if,for any n,n+1,n+2, f(m+1)≤(f(n)+f(n+2). In words,f(n+1)is at most the average of f(n)and f(n +2). Lemma 1.4 summarizes several useful properties of monotonicity and convexity.It states that functions defined only on the integers can be extended to the reals by linear interpolation,preserving properties of monotonicity and convexity.Also,some properties involving derivatives are stated.The proofs are in Exercises 1.17 through 1.19. Lemma 1.4 1.Let f(n)be defined only on integers.Let f*(x)be the extension of f to the reals by linear interpolation between consecutive integers(see Figure 1.3b). a.f(n)is monotonic if and only if f*(x)is monotonic. b.f(n)is convex if and only if f(x)is convex. 2.If the first derivative of f(x)exists and is nonnegative,then f(x)is monotonic. 3.If the first derivative of f(x)exists and is monotonic,then f(x)is convex. 4.If the second derivative of f(x)exists and is nonnegative,then f(x)is convex.(This follows from parts 2 and 3.) Summations Using Integration Several summations that arise often in the analysis of algorithms can be approximated (or bounded from above or below)using integration.First,let us review some useful integration formulas: 1+. k+1 fed-i(-1. (1.15) 中+h侧)-+亚 If f(x)is monotonic (or nondecreasing),then aue2间s广aa 1.16) Similarly,if f(x)is antimonotonic (or nonincreasing),then ea=2Iosed (1.I7)
26 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples f(x)=lgx r0s"fa aa+l 6 641 (a)Overapproximation f(x)=lgx C,s立 a-l a b-1b (b)Underapproximation Figure 1.4 Approximating a sum of values of a monotonic (or nondecreasing)function This situation for monotonic f(x)is illustrated in Figure 1.4.Here are two examples that are used later in the text. Example 1.7 An estimate for i+厂竖=1+n听-1+aa-h1=n+1