A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Chapter 4

These are the solutions to the exercises found in the section, ​Exercises​. The solutions provided here are in Python, but you can find the solutions in JavaScript and Ruby in the code download.^[6]

1. Here is the completed table:

   N Elements	O(N)	O(log N)	O(N2)
   100	100	About 7	10,000
   2000	2000	About 11	4,000,000

2. The array would have 16 elements, since 16² is 256. (Another way of saying this is that the square root of 256 is 16.)

3. The algorithm has a time complexity of O(N²). N, in this case, is the size of the array. We have an outer loop that iterates over the array N times, and for each of those times, an inner loop iterates over the same array N times. This results in N² steps.

4. The following version is O(N), as we only iterate through the array ...