Discrete Mathematics for Computer Science

Exercises 297 Show that: (a) sin(n) E 0(1)-that is, the sine function is asymptotically dominated by the con- stant function 1 ...

298 CHAPTER 5 Analysis of Algorithms (c) Find functions F, G : N --* [0, oc) where O(G) = O(F) but x-o F(x)G(x) does not exist. ...

Complexity of Programs 299 (T(100)), and suppose you need to use this information to estimate how much time P will take on a dat ...

300 CHAPTER 5 Analysis of Algorithms The purely theoretical approach introduced here makes an approximation of the com- plexity ...

Complexity of Programs 301 programming has become a powerful new paradigm for program design, it remains neces- sary to use the ...

302 CHAPTER 5 Analysis of Algorithms Each if-then statement makes a single comparison. Three if-then statements are exe- cuted i ...

Complexity of Programs 303 Complexity of Selection Let n E N. Let a step of an algorithm be to make a selection for execution of ...

304 CHAPTER 5 Analysis of Algorithms concentrate on the selection at line 1. The condition at line^1 requires two comparisons. T ...

Complexity of Programs 305 is a command to repeat operation S over and over, once with i = 1, once with i = 2, ...., and once wi ...

306 CHAPTER 5 Analysis of Algorithms before each time the loop is executed and once again at the end. The result of that final t ...

Complexity of Programs 307 5.3.4 An Algorithm Illustrating Nested Repetition Now look at the entire BubbleSort I algorithm. It i ...

308 CHAPTER 5 Analysis of Algorithms Proof. This proof is left as an exercise for the reader. U One might ask how much more effi ...

Complexity of Programs 309 It is most common to look only at the growth rate-up to O(*)--of the worst-case complexity function. ...

310 CHAPTER 5 Analysis of Algorithms and a truth assignment I to its variables-typically, here, one lists the true literals, suc ...

Complexity of Programs 311 Stephen Cook proved that if propositional satisfiability is in 7), then AfP ___ P. In fact, Cook prov ...

312 CHAPTER 5 Analysis of Algorithms Consider the problem of performing multiplication with arbitrarily large integers. Or- dina ...

Exercises 313 memory. If we have only a fixed number k of processors, then previous complexity bounds are changed by at most 1/ ...

314 CHAPTER 5 Analysis of Algorithms (e) Counter] = 1 while Counter] < X Counter2 = 1 while Counter2 < X S Counter2 = 2 * ...

Exercises 315 (c) For some constants a and b, running the program on a data set of size d always takes a • 2 bd seconds. Write ...

(^316) CHAPTER 5 Analysis of Algorithms Suppose somebody manages to prove that the time taken by some frequently used algorithm ...