Search code examples
javascriptalgorithmbig-ospace-complexity

a question discerning space complexity from newbie


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;
}

Solution

  • 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)