Mathematics for Computer Science

14.7. Asymptotic Notation 433 Proof. lim x!1 g.x/ f.x/ D 1 limx!1f.x/=g.x/ D 1 0 D1; sog¤O.f /.  Proposition 14.7.9.100x^2 DO.x ...

Chapter 14 Sums and Asymptotics434 Definition 14.7.12. fD‚.g/ iff fDO.g/andgDO.f /: The statementf D‚.g/can be paraphrased intui ...

14.7. Asymptotic Notation 435 Constant Confusion Every constant isO.1/. For example, 17 DO.1/. This is true because if we let f. ...

Chapter 14 Sums and Asymptotics436 or nŠD.1Co.1// p 2n n e n : In such cases, the true meaning is HnDln.n/C Cf.n/ for somef.n ...

14.7. Asymptotic Notation 437 Problems for Section 14.1 Class Problems Problem 14.1. We begin with two large glasses. The first ...

Chapter 14 Sums and Asymptotics438 (c)If you plan to retire after twenty years, which degree would be worth more? Problem 14.4. ...

14.7. Asymptotic Notation 439 (^0012345678) 0.5 1 1.5 2 2.5 y = ln(x+2) y = ln(x+1) (^0012345678) 0.2 0.4 0.6 0.8 1 y = 1/(x+1) ...

Chapter 14 Sums and Asymptotics440 Problem 14.7. Use integration to find upper and lower bounds that differ by at most 0.1 for t ...

14.7. Asymptotic Notation 441 Prove that withngallons of water, this strategy will get herHn=2days into the desert and back, whe ...

Chapter 14 Sums and Asymptotics442 (b)Over the firstnseconds, what fraction of the rug does the bug cross altogether? Express yo ...

14.7. Asymptotic Notation 443 Homework Problems Problem 14.14. (a)Prove that logx < xfor allx > 1(requires elementary calc ...

Chapter 14 Sums and Asymptotics444 describes each function’s asymptotic behavior. Full proofs are not required, but briefly expl ...

14.7. Asymptotic Notation 445 Class Problems Problem 14.20. Give an elementary proof (without appealing to Stirling’s formula) t ...

Chapter 14 Sums and Asymptotics446 False Claim. 2 nDO.1/: (14.35) Explain why the claim is false. Then identify and explain the ...

14.7. Asymptotic Notation 447 Problem 14.26. (a)Define a functionf.n/such thatf D‚.n^2 /andNOT.f n^2 /. (b)Define a functiong.n ...

...

15 Cardinality Rules 15.1 Counting One Thing by Counting Another How do you count the number of people in a crowded room? You co ...

Chapter 15 Cardinality Rules450 and close up the gaps: 0011000000100100: We’ve just formed a 16-bit number with exactly 4 ones — ...

15.2. Counting Sequences 451 is the set of all sequences whose first term is drawn fromP 1 , second term is drawn fromP 2 and so ...

Chapter 15 Cardinality Rules452 15.2.3 The Sum Rule Bart allocates his little sister Lisa a quota of 20 crabby days, 40 irritabl ...