CODEWITHSUNDEEP
data-structuresspace-complexity
charan preet
charan preet

Reputation: 13

What is the space complexity of this code

What is the space complexity of the code:

function double(n) {         //Here n is an array
   newArr = [];
   for (i = 0; i < n.length; i++) {
     newArr.push(2 * n[i]);
   }
  return newArr;
}

Upvotes: 0

Views: 385

Answers (2)

smac89
smac89

Reputation: 43118

The space complexity is indeed O(N) because space depends not on how many variables your program has defined but rather on how runtime factors affect memory size.

An exploration of space

Think of the space complexity of an application as a factor of the eventual space requirements of the application.

This factor is determined by your application's memory requirements over various runs of the same application. If the amount of memory an application needs is independent of any variables within the application, then the factor is simply 1 i.e. space complexity of O(1). It is a constant because it does not change. This means that a program that allocates memory depending on user input (such as in your case) will have a seemingly higher space complexity (factor) than a program that only ever allocates 1GB of memory when it starts.

It may sound confusing because you might wonder why your simple program has space complexity of O(N), but a random C application which allocates 1GB of memory at the start is only O(1). Well it all boils down to the factor - if space requirements is dependent on a runtime variable within the program, then the space complexity is a factor of that variable otherwise space is constant.

Upvotes: 3

David G
David G

Reputation: 96810

Since it has two variables newArr and i on which the space of this code depends.

Not only are there two variables named, newArr and i, there are also n variables named newArr[0], newArr[1], newArr[2], all the way to newArr[n-1]. Space complexity refers to the way the storage of your algorithm grows with respect to the number of inputs. Since you're pushing at most n elements into newArr, the space complexity is O(n).

Upvotes: 1

Related Questions