What is O(1) space complexity in term of Javascript code with example

Question

For an example I have below mentioned input and output for function reverseWords()

It's a simple example but this will help me understand. How I will write a function which is In O(1) space for below request ?

// var input = ['H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r'];
// Output(same array): ['o', 'l', 'l', 'e', 'H', ' ', 'r', 'o', 'w']


// In O(1) space complexity 
function reverseWords(input) {

}

reverseWords(input);

How I will write a function which is In O(1) space ? For example -

function reverseString(str) {
    return str.split('').reverse().join('');;
}

reverseString("hello world");

Is this In O(1) Space complexity ? I have referred this What is O(1) space complexity? but still having doubt in terms of understanding in practical way of javascript.

Answer 1

Simply speaking O(1) space complexity means that you use only a constant amount of memory in addition to the passed in values to produce the result.

For example, if you use only a single primitive value in a variable, that would be a constant amount (because it's the same amount, no matter how big your input is)

If your algorithm started with allocating an array as big as the input, then it would not be O(1), but O(n) instead (because the bigger the input the bigger the memory/space requirement is).

So as long as you ensure that your algorithm never allocates anything where the space requirement depends on the size of the input, then your algorithm has O(1) space requirements.

The reason you don't see anything specific to JavaScript in this answer is that big-O notations are pretty much independent of the underlying technology used. Every language will have some way to allocate variable-length things (such as strings as arrays) and fixed-length things ("simple" values such as numbers and booleans).

Answer 2

space complexity of a function says something about how much memory does the function use to produce its output

O(1) space complexity is like saying "The function will not need more than some constant volume of memory regardless of what is on the input"

How much memory the function uses can vary of course but it cannot exceed that maximum

your first example with word reversal can be done "in place" similarly to an array reversal - the elements in the array are only reorganized in the existing memory provided as an input

function reverseArrayInPlace(arr) {
  let el = 0;
  for (var i = 0; i <= Math.floor((arr.length - 1) / 2); i++) {
      el = arr[i];
      arr[i] = arr[arr.length - 1 - i];
      arr[arr.length - 1 - i] = el;
  }
  return arr;
}

the only "memory allocation" the function does is to create 'el' that is reused

the second example where you want to reverse a string cannot be done in javascript - string is immutable (see https://www.sitepoint.com/immutability-javascript/ )so you would have to create a new string of the same length so you would use as much memory as is on the input making the fuction space complexity O(n)

Just one minor thing - real complexity is dependent on the implementation of the compiler/interpreter, when you talk about complexity you usually talk about theoretical complexity as some languages can copy arrays when they are edited etc. Most of the time people do not talk about "complexity in a specific language"

Answer 3

O(1) space complexity means that the amount of memory you need to use to do the operation will not grow relative to the size of the collection that you are operating on. In the context of reversing words, O(1) space complexity would mean that an algorithm would be able to reverse the letters with a constant amount of memory (not necessarily the amount of memory taken up by the array), let's say 1MB, regardless of the length of the word.

In more concrete terms, you could potentially do this by using one extra character as swap space, and swapping letters opposite each other in the array (e.g. in the string 'hello', you would swap 'o' and 'h', then 'e' and 'l'. Because you only need one extra character in memory to do this regardless of the length of string you want to reverse, this counts as O(1) space complexity.