Discrete Mathematics for Computer Science

Chapter Review 277 4.8 Countable and Uncountable Sets TERMS aleph nought (^1 O) countably infinite algebraic finite Cantor's fir ...

278 CHAPTER 4 Functions Which of the sets F 1 , F 2 , and F 3 are onto functions? (a) Fl, F 2 , F 3 (b) F 2 , F 3 (c) F 1 , F 3 ...

Chapter Review 279 If a class has 89 students, how many (at least) must have a birthday on the same day of the week? Of 15 A's, ...

280 CHAPTER^4 Functions exists; (iii) for any x, {x} exists; (iv) for any sets x, y, x U y and x - y exist; and (v) the collecti ...

Chapter Review 281 bers 534-27-3175, 289-13-3754,413-39-4431, 978-65-4891, 534-75-9614. How many students in your class can have ...

...

Analysis of Algorithms We have frequently used the word algorithm to mean the idea, or plan of attack, behind a computer program ...

284 CHAPTER 5 Analysis of Algorithms Finally, we briefly introduce another topic: Are there any functions that are, in princi- p ...

Comparing Growth Rates of Functions 285 Sometimes, two different computers execute various instructions at different relative s ...

286 CHAPTER 5 Analysis of Algorithms Example 2. Let F 1 , G I N --* [ 0, oo )where F, (n) = n and Sn-2 forn>2 0 otherwise as ...

Comparing Growth Rates of Functions 2817 Solution. Here, G 2 (0) is much larger than F 2 (0). For all other values of n, we have ...

288 CHAPTER 5 Analysis of Algorithms y d 60 d G 4 (n) = n^2 d 50 c F(n) = c d a F 4 (n) =a d C 40 x F 4 (n)=x c 30 0 F 4 (n) = n ...

Comparing Growth Rates of Functions 289 (3) F : N -+ [0, cc), given by the rule F(n) = n - 2, is undefined for n = 0, 1 (since 0 ...

290 CHAPTER 5 Analysis of Algorithms NG, and NH that we do not have. However, to verify that H e O(F), we were not required to f ...

Comparing Growth Rates of Functions 291 The relation 0 considers seemingly different functions as being equivalent, at least in ...

292 CHAPTER 5 Analysis of Algorithms Theorem 5. Let kI, k 2 e R with 0 < kl < k 2 .Let xkl and xk2 be functions of x, wher ...

Comparing Growth Rates of Functions 293 Corollary 4: For any integer k > -1 , the polynomial functions in 0(nk) are the polyn ...

294 CHAPTER 5 Analysis of Algorithms Proof. (a) We first establish an inequality involving nk and then define No and c: nk < ...

Comparing Growth Rates of Functions 295 Now, show that n 0 O(ln(n)). Working toward a contradiction, suppose n E O(ln(n)). That ...

296 CHAPTER 5 Analysis of Algorithms U Exercises Find a real number c and an No E N such that n^2 + 5n < cn^2 for all n E N ...