Hands-On Data Structures and Algorithms with JavaScript

Linear space

A linear space algorithm is one in which the amount of space taken by an algorithm is directly proportional to the size of the input, for example, algorithms that loop over an array and push values to a new array before returning them:

function redundant(array) {    var result = [];    for(var i = 0, i < array.size; i++) {        result.push(array[i]);    }    return result;}

As you can see, although redundant, we are creating a new array and pushing all the values into that array, which will use up the same space as that of the input array. Consider the situation in which you have a condition before the push, as shown in the following code:

function notRedundant(array) {    var result = [];    for(var i = 0, i < array.size; i++) { if (someCondition) ...