How to determine the space complexity of a code snippet (Big O)

How to determine the space complexity of a code snippet (Big O)
0

#1

I stumble upon this tutorial, https://www.udemy.com/js-algorithms-and-data-structures-masterclass/learn/v4/content , and it explained how to determine the space complexity of certain code snippet.

For example:

function logUpTo(n) {
    for (var i = 1; i <= n; i++) {
        console.log(i);
    }
}
//O space(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;
}
//O space(n)

I noticed that the tutor said in the second snippet we are dealing with array, and the space complexity of an array is O of n, and n stands for the length of an array.

Can I understand it in this way, we ONLY care about the return functions in those snippets, if it returns an array then it is gonna be O(n) or O(n square) (if there is a nested loop involved), so whenever we try to determine the complexity of code, we only check what kind of value it returns.

Is this a correct understanding about big O??


#2

When we talk about complexity, we are talking about how efficient the algorithm is. Usually we talk about time complexity, which is determined by asking “how many operations will need to be performed in a worse-case scenario?”. It sounds like the person you were learning from was also looking at space complexity which is determined by asking “how much memory would be allocated in a worst-case scenario?”. In either case, it isn’t about the return value (if any) but implimentation of the solution.


#3

I see. Thanks! (20 characters)


#4

I typed a lengthy explanation of the formal definition of the notation but I think that I might explain it in a way that obscures the intuition for it so I’ll instead try the following explanation

If you come up with an algorithm to do something, for example sort a list of numbers, it is important to know how it’s speed scales with the length of the list - if we double the number of elements does the time taken double? Or does it quadruple? Time complexity answers that question

Space complexity refers instead to how much memory is required to perform the algorithm. If we double the number of elements does the amount of memory required to perform the algorithm double?

Sometimes space complexity is discussed as auxillary space complexity, i.e. how much additional space is required (excluding the memory of the list itself)