Mathematics for Computer Science

14.3. Approximating Sums 413 0 1 2 3    n� 2 n� 1 n  ^ f.n/ f.n�1/ f.xC1/ f.3/ f.2/ f.1/ Figure 14.3 This curve is the sam ...

Chapter 14 Sums and Asymptotics414 We then apply Theorem 14.3.2 to conclude that 2 3 .n3=21/C 1  S  2 3 .n3=21/C p n and thus ...

14.4. Hanging Out Over the Edge 415 table Figure 14.4 A stack of 5 identical blocks on a table. The top block is hanging out ove ...

Chapter 14 Sums and Asymptotics416 1=2 table center of mass of block Figure 14.5 One block can overhang half a block length. 14. ...

14.4. Hanging Out Over the Edge 417 overhang table center of mass of whole stack spread Figure 14.6 The overhang is maximized by ...

Chapter 14 Sums and Asymptotics418 top n� 1 blocks bottom block center of mass of top n� 1 blocks center of mass of S Figure 14. ...

14.4. Hanging Out Over the Edge 419 n� 1 blocks 1=2 1 �1= 2n table Figure 14.8 A method for achieving spread (and hence overhang ...

Chapter 14 Sums and Asymptotics420 Case 2:The rightmost block inSis among the topn 1 blocks.In this case, the spread is maximize ...

14.4. Hanging Out Over the Edge 421 1=2 3=4 table (a) 1=4 1=2 table (b) Figure 14.9 Two ways to achieve spread (and hence overha ...

Chapter 14 Sums and Asymptotics422 Both cases give the same spread, albeit by different approaches. For example, see Figure 14.9 ...

14.4. Hanging Out Over the Edge 423 1=8 3=4 1=2 1=6 table (a) 1=8 1=61=4 1=2 table (b) Figure 14.10 The two ways to achieve spre ...

Chapter 14 Sums and Asymptotics424 and so on. This suggests that SnD Xn iD 1 1 2i ; (14.23) which is, indeed, the case. Equation ...

14.4. Hanging Out Over the Edge 425 Because the Harmonic numbers frequently arise in practice, mathematicians have worked hard t ...

Chapter 14 Sums and Asymptotics426 14.5 Products We’ve covered several techniques for finding closed forms for sums but no metho ...

14.5. Products 427 Exponentiating then gives nn en^1  nŠ  nnC^1 en^1 : (14.28) This means thatnŠis within a factor ofnofnn=en^ ...

Chapter 14 Sums and Asymptotics428 Approximation n1 n10 n100 n 1000 p 2n n e
n <10% <1% <0.1% <0.01% p 2n n e ...

14.6. Double Trouble 429 outer sum (which no longer has a summation inside it). For example,^8 X^1 nD 0 yn Xn iD 0 xi ! D X^1 nD ...

Chapter 14 Sums and Asymptotics430 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 ...

14.7. Asymptotic Notation 431 14.7 Asymptotic Notation Asymptotic notation is a shorthand used to give a quick measure of the be ...

Chapter 14 Sums and Asymptotics432 14.7.2 Big Oh Big Oh is the most frequently used asymptotic notation. It is used to give an u ...