Essential Algorithms: A Practical Approach to Computer Algorithms

APPENDIX B

Solutions to Exercises

Chapter 1: Algorithm Basics

1. The outer loop still executes O(N) times in the new version of the algorithm. When the outer loop's counter is i, the inner loop executes O(N − i) times. If you add up the number of times the inner loop executes, the result is N + (N − 1) + (N − 2) + ... + 1 = N × (N − 1) / 2 = (N² − N) / 2. This is still O(N²), although the performance in practice will probably be faster than the original version.
2. See Table B-1. The value Infinity means that the program can execute the algorithm for any practical problem size. The example program Ch01Ex02, which is available for download on the book's website, generates these values.

   Table B-1: Maximum Problem Sizes That Run in Various Times

   

3. The question is, “For what N is 1,500 × N > 30 × N²?” Solving for N gives 50 < N, so the first algorithm is slower if N > 50. You would use the first algorithm if N ≤ 50 and the second if N > 50.
4. The question is, “For what N is N³ / 75 − N² / 4 + N + 10 > N / 2 + 8?” You can solve this in any way you like, including algebra or using Newton's method (see Chapter 2). The two positive solutions to this equation are N < 4.92 and N > 15.77. That means you should use the first algorithm if 5 ≥ N ≥ 15. The Ch01Ex04 example program, which is available for download on the book's website, graphs the two equations and uses Newton's method to find their points ...