CODEWITHSUNDEEP
javascriptspace-complexity
dream123
dream123

Reputation: 129

Space Complexity js functions

What is the space complexity and how we can obtain it? (where a and b are arrays of numbers of size N and M)

a.filter(function(v) {
   return !b.includes(v);
})

Upvotes: 2

Views: 5479

Answers (1)

Ludovit Mydla
Ludovit Mydla

Reputation: 822

Space complexity is a mathematical measure of amount of memory your algorithm/function/program needs to store it's variables. Just like time complexity is measure of how much time your function needs to run.

TL;DR You cannot obtain it by any JS function. It is something you have to "calculate". In your algorithm, using two arrays, the space complexity would be O(n).

Explanation If you want to know bit more about space complexity: In computer science world the space complexity uses the "big Oh" notation (O(something)). And it is something you find out by analyzing your function. Usually by taking a "long hard stare" at your code

For example this function:

function add(x,y) { return x+y; }

Has space complexity of O(1). Because it uses two variables to store its data: x and y. So technically you use two "places" in your memory space. The question is, since you use two places, why the complexity is O(1)? Answer to that is, that complexity is expressed in "scale". That means, that if your function needs 1, 2, 3, ... 5 variables to run we are still talking about "ones" or constants. Therefore O(1) or a "constant complexity".

Another example :

function sum(arr, n) {
  var sum = 0;
  for(var i=0; i<n; i++) {
    sum += arr[i];
  }
}

In this case the space complexity of this function is O(N) Why? Because we are using an array of certain length. This array can have length of 3, but it can also store 100 000 values. Since we are not talking about just "ones" here (or, we cannot be sure that it would be just few values), computer science guys decided that we would denote it as O(N) or "linear complexity".

And so on and on. For example, if you would need a 2D array in your program it would probably have O(N^2) or "quadratic complexity". In some cases you can bump into programs with logarithmic and (hopefully not) "exponential" space complexities of O(log N) or 2^O(N).

Read more about it here, here and here (it's about time comlexity, but the measure is the same)

Upvotes: 9

Related Questions