Mathematics for Computer Science
13.2. Reasoning AboutWhilePrograms 393 ifŒŒTççDT, then hifTthenCelseD; i!hC; i; or ifŒŒTççDF, then hifTthenCelseD; i!hD; ...
Chapter 13 State Machines394 Definition 13.2.5. base cases: ŒŒxWDeççis the function from Env to Env defined by the rule: ŒŒxWD ...
13.2. Reasoning AboutWhilePrograms 395 13.2.4 Logic of Programs A typical program specification describes the kind of inputs and ...
Chapter 13 State Machines396 The rest of the logical rules follow the recursive definition ofwhileprograms. There are axioms for ...
III Counting ...
...
Introduction Counting is useful in computer science for several reasons: Determining the time and storage required to solve a ...
Part III Counting400 the how a quantity such as the running time of a program grows with the size of the input. Chapter 15 descr ...
14 Sums and Asymptotics Sums and products arise regularly in the analysis of algorithms, financial appli- cations, physical prob ...
Chapter 14 Sums and Asymptotics402 we will use this approach to find a good closed-form approximation to thefactorial function n ...
14.1. The Value of an Annuity 403 in two years, and so forth. Looked at another way, ten dollars paid out a year from now is onl ...
Chapter 14 Sums and Asymptotics404 Solving forSgives the desired closed-form expression in equation 14.2, namely, SD 1 xnC^1 1 x ...
14.1. The Value of an Annuity 405 Proof. X^1 iD 0 xiWWDnlim!1 Xn iD 0 xi D lim n!1 1 xnC^1 1 x (by equation 14.2) D 1 1 x : The ...
Chapter 14 Sums and Asymptotics406 tion 14.2 and Theorem 14.1.1: 1 C1=2C1=4CD X^1 iD 0 1 2 i D 1 1 .1=2/ D 2 (14.6) 0:9999 ...
14.1. The Value of an Annuity 407 differentiating equation 14.2 leads to: d dx (^) n 1 X iD 0 xi ! D d dx 1 xn 1 x : (14.11) ...
Chapter 14 Sums and Asymptotics408 Theorem 14.1.2.Ifjxj< 1, then X^1 iD 1 ixiD x .1x/^2 : (14.13) As a consequence, suppose t ...
14.2. Sums of Powers 409 It turns out that there is a way to derive these expressions, but before we explain it, we thought it w ...
Chapter 14 Sums and Asymptotics410 Solving this system gives the solutionaD 1=3,b D1=2,c D 1=6,d D 0. Therefore,if our initial g ...
14.3. Approximating Sums 411 Similarly,f isstrictly decreasingwhen x < yIMPLIESf.x/ > f.y/; and it isweakly decreasing^6 w ...
Chapter 14 Sums and Asymptotics412 0 1 2 3 ^ n� 2 n� 1 n f.n/ f.n�1/ f.3/ f.2/ f.1/ Figure 14.1P The area of theith re ...
«
16
17
18
19
20
21
22
23
24
25
»
Free download pdf
