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

Chapter 3

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

1. This is O(1). We can consider N to be the year passed into the function. But no matter what the year is, the algorithm doesn’t vary in how many steps it takes.

2. This is O(N). For N elements in the array, the loop will run N times.

3. This is O(log N). In this case, N is the number numberOfGrains, which is passed into the function. The loop runs as long as placedGrains < numberOfGrains, but placedGrains starts at 1 and doubles each time the loop runs. If, for example, numberOfGrains was 256, we’d keep doubling the placedGrains nine times until we reach 256, meaning that our loop would run eight times for an N of 256. If numberOfGrains was 512, our loop would run nine ...