Mathematics for Computer Science
13.3. Approximating Sums 513 0 1 2 3 ^ n� 2 n� 1 n f.n/ f.n�1/ f.3/ f.2/ f.1/ Figure 13.1P The area of theith rectangl ...
Chapter 13 Sums and Asymptotics514 0 1 2 3 n� 2 n� 1 n ^ f.n/ f.x/ f.n�1/ f.3/ f.2/ f.1/ Figure 13.2 The shaded area u ...
13.3. Approximating Sums 515 0 1 2 3 n� 2 n� 1 n ^ f.n/ f.n�1/ f.xC1/ f.3/ f.2/ f.1/ Figure 13.3 This curve is the sam ...
Chapter 13 Sums and Asymptotics516 13.4 Hanging Out Over the Edge Suppose you have a bunch of books and you want to stack them u ...
13.4. Hanging Out Over the Edge 517 table center of mass of the whole stack overhang Figure 13.5 Overhanging the edge of the tab ...
Chapter 13 Sums and Asymptotics518 table } 2(n+1) 1 topnbooks } center of mass center of mass of topnbooks of alln+1 books Figur ...
13.4. Hanging Out Over the Edge 519 13.4.2 Harmonic Numbers Definition 13.4.1.Thenthharmonic number,Hn, is HnWWD Xn iD 1 1 i : S ...
Chapter 13 Sums and Asymptotics520 Here is a value0:577215664:::calledEuler’s constant, and.n/is between 0 and 1 for alln. We w ...
13.4. Hanging Out Over the Edge 521 1=2 3=4 table (a) 1=4 1=2 table (b) Figure 13.8 Figure (a) shows a stable stack of two books ...
Chapter 13 Sums and Asymptotics522 the leading term ofHnis ln.n/. More precisely: Definition 13.4.2.For functionsf;gWR!R, we say ...
13.5. Products 523 We can then apply our summing tools to find a closed form (or approximate closed form) for ln.P/and then expo ...
Chapter 13 Sums and Asymptotics524 Theorem 13.5.1 can be proved by induction (with some pain), and there are lots of proofs usin ...
13.6. Double Trouble 525 Approximation n1 n10 n100 n 1000 p 2n n e n <10% <1% <0.1% <0.01% p 2n n e n e1=12n ...
Chapter 13 Sums and Asymptotics526 outer sum (which no longer has a summation inside it). For example,^5 X^1 nD 0 yn Xn iD 0 xi ...
13.6. Double Trouble 527 we are summing, they form a triangle: j 1 2 3 4 5 ::: n k 1 1 2 1 1=2 3 1 1=2 1=3 4 1 1=2 1=3 1=4 ::: n ...
Chapter 13 Sums and Asymptotics528 13.7 Asymptotic Notation Asymptotic notation is a shorthand used to give a quick measure of t ...
13.7. Asymptotic Notation 529 13.7.2 Big O Big O is the most frequently used asymptotic notation. It is used to give an upper bo ...
Chapter 13 Sums and Asymptotics530 We need lim sup’s in Definition 13.7.5 to cover cases when limits don’t exist. For example, i ...
13.7. Asymptotic Notation 531 that it is a better choice. TheO.n2:55/-operation multiplication procedure is almost never used in ...
Chapter 13 Sums and Asymptotics532 13.7.4 Pitfalls with Asymptotic Notation There is a long list of ways to make mistakes with a ...
«
22
23
24
25
26
27
28
29
30
31
»
Free download pdf