Exercises

The following exercises provide you with the opportunity to practice with speeding up your code. The solutions to these exercises are found in the section .

1. Replace the question marks in the following table to describe how many steps occur for a given number of data elements across various types of Big O:

   N Elements	O(N)	O(log N)	O(N2)
   100	100	?	?
   2000	?	?	?

2. If we have an O(N²) algorithm that processes an array and find that it takes 256 steps, what is the size of the array?

3. Use Big O notation to describe the time complexity of the following function. It finds the greatest product of any pair of two numbers within a given array:

   ​	​def​ ​greatest_product​(array):
   ​	​if​ len(array) < 2:
   ​	​return​ None
   ​
   ​	greatest_product_so_far = array[0] * array[1]
   ​
   ​	​for​ index_i, value_i ​in​ enumerate(array):
   ​	​for​ index_j, value_j ​in​ enumerate(array):
   ​	​if​ (index_i != index_j ​and​
   ​	value_i * value_j > greatest_product_so_far):
   ​	greatest_product_so_far = value_i * value_j
   ​
   ​	​return​ greatest_product_so_far

4. The following function finds the greatest single number within an array, but it has an efficiency of O(N²). Rewrite the function so that it becomes a speedy O(N):

   ​	​def​ ​greatest_number​(array):
   ​	​if​ ​not​ array:
   ​	​return​ None
   ​
   ​	​for​ i ​in​ array:
   ​	​# Assume for now that i is the greatest:​
   ​	is_i_the_greatest = True
   ​
   ​	​for​ j ​in​ array:
   ​	​# If we find another value that is greater than i,​
   ​	​# i is not the greatest:​
   ​	​if​ j > i:
   ​	is_i_the_greatest = False
   ​
   ​	​# If, by the time we checked all the other numbers, i​
   ​	​# is still the greatest, it means that i is the greatest number:​
   ​	​if​ is_i_the_greatest:
   ​	​return​ i