Blog / Data Structures & Algorithms
Space Complexity
  • Nov 24, 2020
  • 57
  • 59

Beside time complexity, space complexity is another measurement to determine if you code is a good one. When we talk about time complexity, we are referring to the speed of your algorithm, or in other words, how many operations does it cost. For space complexity, it is about the memory your algorithm needs to execute.


Advertisement
 


1. What is Space Complexity

Space complexity is a measure of the amount of working storage an algorithm needs.

That means how much memory, in the worst case, is needed at any point in the algorithm. As with time complexity, we're mostly concerned with how the space needs grow, in big O terms, as the size N of the input problem grows.

When a program executes, the are two ways to remember things: the heap and the stack. The heap is usually where the computers store variables the we assign values to and the stack is usually where we keep tracks of the function calls.

2. Space Complexity Causes

So, what causes space complexity? Below are the causes:

  • Variables
  • Data Structures
  • Function Call
  • Allocations

We will understand more the causes by looking at the example below:

function Func1(array) {
   for (let i = 0; i < array.length; i++) { // O(1) for let i = 0
      console.log('hello');
   }
}
 
Func1([1,2,3,4,5]); //Space Complexity: O(1)

When we talk about space complexity, we talk about additional space needed to execute the function. Therefore, we don't care about space taken up by the input. For the above function, we don't really add anymore memory beside adding a variable i = 0 in a for loop. So, the above function costs O(1) space complexity.

Let's consider another function below:

function Func2(array) {
   let anotherArray = [];
 
   for (let i = 0; i < array.length; i++) { // O(1) for let i = 0
      anotherArray[i] = 'Hello'; // O(n) for adding value to anotherArray n times (n is size of array)
   }
 
   return anotherArray;
}
 
Func2([1,2,3,4,5]); //Space complexity is O(n)

In the above function, we create a new data structure which is an array. Then, we add value to the new array n times where n is the size of the input. So, the above function costs O(n) space complexity.

Read more in this series:


Using cherry-pick to select specific commits for your Pull Request.1. Create a new branch based on the target of the Pull Requestgit branch cherry-branch origin/master2. Switch to a new branchgit chec ...

After deployment Angular and API on IIS, it's working fine unless I refresh the page. Once refreshed, the web encountered 404 error. In this article, I will explain how to resolve this.Since Angular i ...

There are some benefits of keeping both UI and API parts in the same place for small projects. In this article, I will explain how I did to deploy Angular Web and ASP .Net Core API in the same folder ...

I got CORS error after publishing my API and Angular app to IIS even though CORS is enabled and the origins of the Angular app is added. Below is how I resolved this issue.Just simple, make sure you s ...

In Object-Oriented Programming, S.O.L.I.D refers to the first five design principle for the purpose of making software designs more understandable, flexible, and maintainable. The principles was first ...

1. The Situation:Error Message:&nbsp;Pulse Secure Application failed to load Java. Please install correct JRE version.Description: This issue happens when I'm using a M1 Mac with a correct version of ...

Accelerated Mobile Pages (AMP)&nbsp;focuses on delivering static content from publishers as quickly as possible and possibly rewards early adopters with a boost in rank. Let's see how to implement it ...

Below is how to decrypt/convert a Hex string value into text using VB.Net:Decrypting Hex string value to string in VB.Net Function HexToString(ByVal hex As String) As String Dim text As New Sy ...

After a month of publishing on Google Play, Jungle Words has made it to the Top Android Games To Try Out In April 2021. Please check it out!&nbsp;GameKeys.netGameKeys is a website which introduces gam ...