Exercises

The following exercises provide you with the opportunity to practice with optimizing for best- and worst-case scenarios. The solutions to these exercises are found in the section .

1. Use Big O notation to describe the efficiency of an algorithm that takes 3N² + 2N + 1 steps.

2. Use Big O notation to describe the efficiency of an algorithm that takes N + log N steps.

3. The following function checks whether an array of numbers contains a pair of two numbers that add up to 10.

   ​	​def​ ​two_sum​(array):
   ​	​for​ index_i, i ​in​ enumerate(array):
   ​	​for​ index_j, j ​in​ enumerate(array):
   ​	​if​ (index_i != index_j) ​and​ (i + j == 10):
   ​	​return​ True
   ​
   ​	​return​ False

   What are the best-, average-, and worst-case scenarios? Then, express the worst-case scenario in terms of Big O notation.

4. The following function returns whether or not a capital “X” is present within a string.

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

   What is this function’s time complexity in terms of Big O notation?

   Then, modify the code to improve the algorithm’s efficiency for best- and average-case scenarios.