A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Chapter 19

These are the solutions to the exercises found in the section, ​Exercises​. The solutions provided here are in JavaScript, but you can find the solutions in Python and Ruby in the code download.^[18]

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 newArray 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, ...