A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Chapter 4

These are the solutions to the exercises found in the section ​Exercises​.

1. Here is the completed table:

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

2. The array would have sixteen 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 once:

   function greatestNumber(array) {
     if (array.length === 0) { return null; }
   
     let greatestNumberSoFar ...