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

Chapter 7

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

1. Here, N is the size of the array. Our loop runs for N / 2 times, as it processes two values each round of the loop. However, this is expressed as O(N) because we drop the constant.

2. It’s slightly tricky to define N in this case, since we’re dealing with two distinct arrays. The algorithm only processes each value once, so we could decide to call N the total number of values between both arrays, and the time complexity would be O(N). If we want to be more literal and call one array N and the other M, we could alternatively express the efficiency as O(N + M). However, because we’re simply adding N and M together, it’s simpler to just use N to refer to the total ...