Mathematics for Computer Science
13.7. Asymptotic Notation 533 Similarly, you will often see statements like HnDln.n/C CO 1 n or nŠD.1Co.1// p 2n n e n In ...
Chapter 13 Sums and Asymptotics534 For example,x^2 D.x/, 2 xD.x^2 /, andx=100D.100xC p x/. So if the running time of your alg ...
13.7. Asymptotic Notation 535 You’ve seen this neat trick for evaluating a geometric sum: SD 1 CzCz^2 C:::Czn zSDzCz^2 C:::CznCz ...
Chapter 13 Sums and Asymptotics536 (a)How much is a Harvard degree worth today if the holder will work fornyears following gradu ...
13.7. Asymptotic Notation 537 Using the Integral Method of Section 13.3, we can find integers,a,b,c,d, and a real number,e, such ...
Chapter 13 Sums and Asymptotics538 (^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/( ...
13.7. Asymptotic Notation 539 Homework Problems Problem 13.10. Letf WRC!RCbe a weakly decreasing function. Define SWWD Xn iD 1 f ...
Chapter 13 Sums and Asymptotics540 day to the shrine, grabs the Holy Grail, and then walks for2=3of a day back to the oasis—agai ...
13.7. Asymptotic Notation 541 a malicious first-grader named Mildred Andersonstretchesthe rug by 1 meter. As- sume that her acti ...
Chapter 13 Sums and Asymptotics542 by each of the expressions below. (a)2x^3 C.logx/x^2 (b)2x^2 +.logx/x^3 (c).1:1/x (d).0:1/x ( ...
13.7. Asymptotic Notation 543 Problem 13.19. Show that ln.n^2 Š/D‚.n^2 lnn/ Hint:Stirling’s formula for.n^2 /Š. Problem 13.20. T ...
Chapter 13 Sums and Asymptotics544 Problem 13.23. Indicate which of the following holds for each pair of functions.f.n/;g.n//in ...
13.7. Asymptotic Notation 545 (c) Xn iD 0 2 2iC^1 (d) ln.n^2 Š/ (e) Xn kD 1 k 1 1 2 k Problem 13.26. (a)Either prove or dis ...
Chapter 13 Sums and Asymptotics546 (a)Prove that2f 2g. (b)Prove thatf^2 g^2. (c)Give examples off andgsuch that 2 f6 2 g. Pro ...
13.7. Asymptotic Notation 547 base case:P.0/holds trivially. inductive step:We may assumeP.n/, so there is a constantc > 0suc ...
Chapter 13 Sums and Asymptotics548 (b)You may assume that iff.n/ 1 andg.n/ 1 for alln, thenf g! f (^1) n g (^1) n . Show tha ...
13.7. Asymptotic Notation 549 f DO.g/AND NOT.gDO.f //. (b)Indicate the implications among the assertions in part (a). For examp ...
...
14 Cardinality Rules 14.1 Counting One Thing by Counting Another How do you count the number of people in a crowded room? You co ...
Chapter 14 Cardinality Rules552 and close up the gaps: 0011000000100100: We’ve just formed a 16-bit number with exactly 4 ones—a ...
«
23
24
25
26
27
28
29
30
31
32
»
Free download pdf