Can someone explain why the space complexity of this algo is O(n) and not O(1)?
function subtotals(array) {
var subtotalArray = Array(array.length);
for (var i = 0; i < array.length; i++) {
var subtotal = 0;
for (var j = 0; j <= i; j++) {
subtotal += array[j];
}
subtotalArray[i] = subtotal;
}
return subtotalArray;
}
You're creating a new element in subtotalArray
for every item in the array
parameter. So if you have 1000 items in the input array, the output array will require a certain amount of memory, let's say X. If you have 100,000 items in the input array, the output array will require 100* X memory, or thereabouts.
(There's also the subtotal
number that gets created on every iteration)