Chapter 4

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

1. Here is the completed table:

   N Elements	O(N)	O(log N)	O(N2)
   100	100	About 7	10,000
   2000	2000	About 11	4,000,000

2. The array would have sixteen elements, since 16² is 256. (Another way of saying this is that the square root of 256 is 16.)

3. The algorithm has a time complexity of O(N²). N, in this case, is the size of the array. We have an outer loop that iterates over the array N times, and for each of those times, an inner loop iterates over the same array N times. This results in N² steps.

4. The following version is O(N), as we only iterate through the array once:

   ​	​def​ ​greatest_number​(array):
   ​	​if​ ​not​ array:
   ​	​return​ None
   ​
   ​	greatest_number_so_far = array[0]
   ​
   ​	​for​ i ​in​ array:
   ​	​if​ i > greatest_number_so_far:
   ​	greatest_number_so_far = i
   ​
   ​	​return​ greatest_number_so_far