Exercises

The following exercises provide you with the opportunity to practice with space constraints. The solutions to these exercises are found in the section .

1. Following is the word builder algorithm we encountered in . Describe its space complexity in terms of Big O:

   ​	​def​ ​word_builder​(array):
   ​	collection = []
   ​
   ​	​for​ index_i, i ​in​ enumerate(array):
   ​	​for​ index_j, j ​in​ enumerate(array):
   ​	​if​ index_i != index_j:
   ​	collection.append(i + j)
   ​
   ​	​return​ collection

2. Following is a function that reverses an array. Describe its space complexity in terms of Big O:

   ​	​def​ ​reverse​(array):
   ​	new_array = []
   ​
   ​	​for​ value ​in​ array:
   ​	new_array.insert(0, value)
   ​
   ​	​return​ new_array

3. Create a new function to reverse an array that takes up just O(1) extra space.

4. Following are three different implementations of a function that accepts an array of numbers and returns an array containing those numbers multiplied by 2. For example, if the input is [5, 4, 3, 2, 1], the output will be [10, 8, 6, 4, 2].

   ​	​def​ ​double_array_1​(array):
   ​	new_array = []
   ​
   ​	​for​ value ​in​ array:
   ​	new_array.append(value * 2)
   ​
   ​	​return​ new_array
   ​
   ​
   ​	​def​ ​double_array_2​(array):
   ​	​for​ i ​in​ range(len(array)):
   ​	array[i] *= 2
   ​
   ​	​return​ array
   ​
   ​
   ​	​def​ ​double_array_3​(array, index=0):
   ​	​if​ index >= len(array):
   ​	​return​
   ​
   ​	array[index] *= 2
   ​	double_array_3(array, index + 1)
   ​
   ​	​return​ array

   Fill in the table that follows to describe the efficiency of these three versions in terms of both time and space:

   Version	Time Complexity	Space Complexity
   Version #1	?	?
   Version #2	?	?
   Version #3	?	?