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 plexity 
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 plexity ? I have referred this What is O(1) space plexity? but still having doubt in terms of understanding in practical way of javascript.

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 plexity 
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 plexity ? I have referred this What is O(1) space plexity? but still having doubt in terms of understanding in practical way of javascript.

• javascript
• arrays
• ecmascript-6
• big-o
• space-plexity

• what do you mean with space? on which value is it ment? – Nina Scholz Commented Aug 6, 2019 at 10:49
• 4 He means space plexity @NinaScholz – Liam Commented Aug 6, 2019 at 10:50
• right, but which space? – Nina Scholz Commented Aug 6, 2019 at 10:50
• 1 You referring auxiliary space used by algorithm or the total space used (space plexity) ? – Code Maniac Commented Aug 6, 2019 at 10:52
• 2 @JavascriptCoder well O(1) means using a fix amount of space, irrespective of input size, i.e. let's say you're adding a array of numbers so you're just using a single variable to store total, no matter how much big your input arrays gets – Code Maniac Commented Aug 6, 2019 at 10:58

3 Answers 3

Simply speaking O(1) space plexity 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).

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

O(1) space plexity 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./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 plexity O(n)

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

O(1) space plexity 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 plexity 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 plexity.