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

Exercises

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

1. Following is the “Word Builder” algorithm we encountered in ​Word Builder​. Describe its space complexity in terms of Big O:

   function wordBuilder(array) {
     let collection = [];
   
     for(let i = 0; i < array.length; i++) {
       for(let j = 0; j < array.length; j++) {
         if (i !== j) {
           collection.push(array[i] + array[j]);
         }
       }
     }
   
     return collection;
   }

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

   function reverse(array) {
     let newArray = [];
   
     for (let i = array.length - 1; i >= 0; i--) ...