Chapter 7

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

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 number of data elements across both arrays and call it O(N).

3. In a worst-case scenario, this algorithm runs (approximately) as many times as the number of characters in the needle multiplied by the number of characters in the haystack. Imagine, for example, that we’re searching for the needle ab within the haystack aaaaaaaaaaab. Every time our outer loop reaches a new a, we run an inner loop looking for ab.

   Since the needle and haystack may have different numbers of characters, this is O(N * M).

4. N is the size of the array, and the time complexity is O(N³), as it’s processed through triply-nested loops. Really, the middle loop runs N / 2 times, and the innermost loop runs N / 4 times, so this is N * (N / 2) * (N / 4), which is N³ / 8 steps. But we drop the constant, leaving us with O(N³).

5. N is the size of the resumes array. Since in each round of the loop we eliminate half of the resumes, we have an algorithm of O(log N).