Space complexity

Table of contents

Automate your business at $5/day with Engati

REQUEST A DEMO
space complexity

What is space complexity?

Space complexity is pretty much a measurement of the total amount of memory that algorithms or operations need to run according to their input size. It is essentially the  amount of memory space that the algorithm requires to solve an instance of the computational problem as a function of characteristics of the input.

It is the memory that the algorithm requires till it is fully executed.

Space complexity is often mistaken for Auxilary Space. But there is a difference between them. Auxiliary space is just a part of space complexity. Auxiliary space refers to the extra space or the temporary space that an algorithm uses. Space complexity is the total space taken up by the algorithm with respect to the input size. Space complexity includes auxiliary space as well as the space used by input.

Space complexity = Auxiliary space + Input space.

Space complexity is essentially a parallel concept to time complexity. If you need to create an array of size n, this will take O(n) space. If you build a two-dimensional array of size n*n, this will need O(n2) space.

Space complexity is dependent on several factors. These include the programming language, the compiler, as well as the machine that runs the algorithm.

space complexity
Source: DEV Community


What does an algorithm use memory space for?

What does an algorithm use memory space for?

There are three purposes for which an algorithm uses memory space while executing::

Instruction space

This is the amount of space that is utilized for saving the compiled version of instructions. 

Environmental Stack

An algorithm(function) could be inside another algorithm(function). In such circumstances, the current variables will get pushed onto the system stack, where it waits for further execution and the call to the inside algorithm(function) gets made.

Let's say that a function A() calls function B() that is inside it. In this situation, all the variables of the function A() will be temporarily stored on the system stack while the function B() gets called and executed inside the function (A).

Data space

This is the amount of space that is used by the variables and the constants. 

While space complexity is calculated, only the data space is considered. The instruction space and the environmental stack is ignored.

3x your revenue with Chatbots and Live Chat
Schedule a demo


How important is space complexity?

Application developers are bound by the physical memory of the systems that they intend to run the applications on. That’s why space complexity is extremely important. You do not ever want to run a function or process that goes over the amount of space the system has at any point.


Which notations are used to express space complexity measurements?

Notations used to express space complexity measurements

Big-O Notation

This notation describes an asymptotic upper bound of the asymptotic Notations. It denotes the algorithms scalability and performance. It essentially gives you the worst-case scenario of an algorithm’s growth rate. What it tells you is that the amount of space that the algorithm in question takes will not grow any faster than this f(x), but it could grow at a slower pace.

Here are some examples of expressing space complexity using big-O notation, starting from the slowest space growth to the fastest. 

  • O(1): This signifies constant complexity. It takes the same amount of space irrespective of the input size.
  • O(log n): This signifies logarithmic complexity. It takes up space proportional to the log of the input size.
  • O(n): This denotes linear complexity. It takes space directly proportional to the input size.
  • O(n log n):This denotes log-linear or quasilinear complexity. It is also called linearithmic. Its space complexity increases proportionally to the input size and a logarithmic factor.
  • O(n2): This denotes square or polynomial complexity. Space complexity increases proportionally to the square of the input size.

Omega Notation – Ω

The omega notation describes an asymptotic lower bound. It essentially gives you the best-case scenario of the algorithm’s growth rate. Essentially, it says that the amount of space that the algorithm in question takes will not grow any slower than this f(x), but it could grow at a faster pace.

Theta Notation – θ

The Theta notation represents a function that lies within upper and lower bounds. It can say that the algorithm in question will take up at least this much space (the lower bound) and no more than this amount of space (the maximum) amount of space.

How do you calculate space complexity?

The are two kinds if algorithms that you’d have to calculate space complexity for. 

Iterative Algorithms

With these, you’d need to consider the variables and data structures that are declared in your program. 

As an example, declaring an array of size n would cause the space complexity to rise by a factor of O(n). a 2D array would increase the space complexity by a factor of O(n^2) and so on. Simple variables always add a space complexity of O(1) because the size of a specific datatype will always be constant. 

User defined datatypes tend to be trickier, but most of the time, iterative algorithms tend to be straightforward to analyse in terms of space complexity.

Recursive Algorithms

Recursive algorithms can be trickier since on top of taking care of the variables and data structures (memory reserved for operations in the heap), you would also have to handle the stack memory that is used for recursive calls.

You can take the Fibonacci algorithm as an example. Here F(n) = F(n-1) + F(n-2), n>2. On tracing out the  recursive calls you will see that the program doesn’t occupy upwards of n cells in the stack memory for a function call of F(n).

If you assume that every cell in the stack reserves equal space, then you could say that this algorithm has a space complexity of O(n)

Close Icon
Request a Demo!
Get started on Engati with the help of a personalised demo.
Thanks for the information.
We will be shortly getting in touch with you.
Oops! something went wrong!
For any query reach out to us on contact@engati.com
Close Icon
Congratulations! Your demo is recorded.

Select an option on how Engati can help you.

I am looking for a conversational AI engagement solution for the web and other channels.

I would like for a conversational AI engagement solution for WhatsApp as the primary channel

I am an e-commerce store with Shopify. I am looking for a conversational AI engagement solution for my business

I am looking to partner with Engati to build conversational AI solutions for other businesses

continue
Finish
Close Icon
You're a step away from building your Al chatbot

How many customers do you expect to engage in a month?

Less Than 2000

2000-5000

More than 5000

Finish
Close Icon
Thanks for the information.

We will be shortly getting in touch with you.

Close Icon

Contact Us

Please fill in your details and we will contact you shortly.

Thanks for the information.
We will be shortly getting in touch with you.
Oops! Looks like there is a problem.
Never mind, drop us a mail at contact@engati.com