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

[mrchow19910319]

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??

[Franck]

Big O doesn't really have to do with return value. It's the growth rate of the method based on the amount of element passed.

If you pass many elements and it ran only 1 of them then it's O(1)

If you pass many elements and it ran all of them once it's O(n)

If you pass many elements and it went through the array twice O(2n)

 

There is also 2 ways to use it. This one is for programing but i remember back in school (long time ago) math also had Big O but i don't think it was the same.

If you freeze on this subject you can pass over it. In 26 years i haven't encounter a single time were it was useful to know which one it was exactly it is. You really only need to know that it doesn't iterate the amount it time it should be and then find and fix the bug.

[reniat]

1 hour ago, mrchow19910319 said:

we only check what kind of value it returns.

Is this a correct understanding about big O??

consider the case where you have a function that returns a boolean: true if a given array has duplicates, false if it contains only unique elements. You're going to have to use the array to find the answer, so at least O(N) space complexity where n is the size of the array, however your return value is only ever going to be a single byte of memory (typically).

[Mira Yurizaki]

1 hour ago, mrchow19910319 said:

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??

For space complexity, no. It depends on the intermediate data the algorithm needs. Even if this function returns a single byte value, the Big-O for space complexity is still O(n) because it's generating a list of n elements as intermediate data. I would also argue the input data has an impact on the space complexity, but for the purposes of analyzing just the algorithm itself, only the intermediate data matters.

 

If we're talking about computational complexity, then this algorithm is actually larger than O(n), because of the inner loop.

[wasab]

On 10/4/2018 at 3:03 PM, M.Yurizaki said:

For space complexity, no. It depends on the intermediate data the algorithm needs. Even if this function returns a single byte value, the Big-O for space complexity is still O(n) because it's generating a list of n elements as intermediate data. I would also argue the input data has an impact on the space complexity, but for the purposes of analyzing just the algorithm itself, only the intermediate data matters.

 

If we're talking about computational complexity, then this algorithm is actually larger than O(n), because of the inner loop.

What O(n) is this? (Actual question on my exam)

https://www.google.com/amp/s/www.technical-recipes.com/2015/determining-if-paths-are-hamiltonian-in-c/amp/

 

[PeterBocan]

@wasab well, it looks like it is a recursive graph traversing. It looks like DFS, which is O(n+m) as a part of the backtracking mechanism for solving the HP problem with DP.