Chapter 6

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

1. In Big O notation, 2N² + 2N + 1 gets reduced to O(N²). After getting rid of all the constants, we’re left with N² + N, but we also drop the N since it’s a lower order than N².

2. Since log N is a lower order than N, it’s simply reduced to O(N).

3. The important thing to note here is that the function ends as soon as we find a pair that sums to 10. The best-case scenario, then, is when the first two numbers add up to 10, since we can end the function before the loops even get underway. An average-case scenario may be when the two numbers are somewhere in the middle of the array. The worst-case scenarios are when there aren’t any two numbers that add up to 10, in which case we must exhaust both loops completely. This worst-case scenario is O(N²), where N is the size of the array.

4. This algorithm has an efficiency of O(N), as the size of the array is N, and the loop iterates through all N elements.

   This algorithm continues the loop even if it finds an “X” before the end of the array. We can make the code more efficient if we return True as soon as we find an “X”:

   ​	​def​ ​contains_X​(string):
   ​	​for​ char ​in​ string:
   ​	​if​ char == ​"X"​:
   ​	​return​ True
   ​
   ​	​return​ False