Chapter 5

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

1. After dropping the constants, we can reduce the expression to O(N).

2. After dropping the constant, we can reduce the expression to O(N²).

3. This algorithm is one of O(N), with N being the size of the array. While there are two distinct loops that process the N elements, this is simply 2N, which is reduced to O(N) after dropping the constants.

1. This algorithm is one of O(N), with N being the size of the array. Within the loop, we run three steps, which means our algorithm takes 3N steps. However, this is reduced to O(N) when we eliminate the constants.

2. This algorithm is one of O(N²), with N being the size of the array. While we only run the inner loop half of the time, this simply means that the algorithm runs for N² / 2 steps. However, the division by 2 is a constant, so we express this simply as O(N²).