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.

Anything I add here is just going to duplicate what is already said in that question — Liam, Aug 06 '19 at 10:50
As its says - code does not grow with the input or the size of the data — Javascript Coder, Aug 06 '19 at 10:52
You referring `auxiliary space` used by algorithm or the total space used (space complexity) ? — Code Maniac, Aug 06 '19 at 10:52
@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, Aug 06 '19 at 10:58
Not what you are looking for but just got curious as to how I would do it: ```['H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r'].join('').split(' ').map(x => x.split('').reverse()).join(', ,').split(',')``` — acesmndr, Aug 06 '19 at 10:59
@NinaScholz I just wanted to know how we are calculating space here or in any algo ? — Javascript Coder, Aug 06 '19 at 11:07
@NinaScholz My solution doesn't adhere the space complexity that the user wanted. It just allocates new memory for each operations. — acesmndr, Aug 06 '19 at 11:11

score 6 · Answer 1 · answered Aug 06 '19 at 10:54

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).

Derte Trdelnik · Answer 2 · 2019-08-06T12:56:30.910

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"

The function you have written will not solve the problem, if you see carefully desired output is reversed words not the complete array, see carefully `['o', 'l', 'l', 'e', 'H', ' ', 'r', 'o', 'w']`, — Code Maniac, Aug 06 '19 at 11:17
yes you are correct, did not notice that I will edit to indicate it, but will probably keep the simple array reverse as the question is about space complexity and having a more complicated code would just be confusing — Derte Trdelnik, Aug 06 '19 at 12:47

score 1 · Answer 3 · answered Aug 06 '19 at 10:57

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.

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

3 Answers3