Essential Algorithms, 2nd Edition

APPENDIX BSolutions to Exercises

Chapter 1: Algorithm Basics

1. The outer loop still executes times in the new version of the algorithm. When the outer loop's counter is i, the inner loop executes times. If you add up the number of times that the inner loop executes, the result is This is still 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 programs Ch01Ex02 and ch01_ex02, which are available for download on the book's website, generate these values.

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

   TIME	LOG2(N)	SQRT(N)	N	N2	2N	N!
   Second	Infinity			1,000	20	10
   Minute	Infinity			...