Chapter 19

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

1. The space complexity is O(N²). This is because the function creates the array called collection, which will end up holding N² strings.

2. This implementation takes up O(N) space, as we create a new_array containing N items.

3. The following implementation uses this algorithm: we swap the first item with the last item in place. Then we swap the second item with the second-to-last item in place. We then proceed to swap the third item with the third-to-last item in place, and so on. Since everything is done in place and we don’t create any new data, this has a space complexity of O(1).

   ​	​def​ ​reverse​(array):
   ​	i = 0
   ​
   ​	​while​ i < len(array) // 2:
   ​	mirror_of_i = len(array) - 1 - i
   ​	array[i], array[mirror_of_i] = array[mirror_of_i], array[i]
   ​
   ​	i += 1
   ​
   ​	​return​ array

   (While Python may, under the hood, be creating a temporary variable to accomplish each swap, we never have more than that one piece of data stored at any time during the algorithm’s execution.)

4. Here’s the completed table:

   Version	Time Complexity	Space Complexity
   Version #1	O(N)	O(N)
   Version #2	O(N)	O(1)
   Version #3	O(N)	O(N)

   All three versions run for as many steps as there are numbers in the array, so the time complexity is O(N) for all of them.

   Version #1 creates a brand-new array to store the doubled numbers. This array will have the same length as the original array, so takes up O(N) space.

   Version #2 modifies the original array in place, so takes up zero extra space. This is expressed as O(1).

   Version #3 also modifies the original array in place. However, since the function is recursive, the call stack at its peak will have N calls on it, taking up O(N) space.