Chapter 3

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

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 number_of_grains, which is passed into the function. The loop runs as long as placed_grains < number_of_grains, but placed_grains starts at 1 and doubles each time the loop runs. If, for example, number_of_grains was 256, we’d keep doubling the placed_grains nine times until we reach 256, meaning that our loop would run eight times for an N of 256. If number_of_grains was 512, our loop would run nine times, and if number_of_grains was 1024, the loop would run ten times. Since our loop runs only one more time each time N is doubled, this is considered O(log N).

4. This is O(N). N is the number of strings within the array, and the loop will take N steps.

5. This is O(1). We can consider N to be the size of the array, but the algorithm takes a fixed number of steps no matter what N is. The algorithm does account for whether N is even or odd, but in either case, it takes the same number of steps.