We launched our first course, Introduction to Data Structures in C++! Learn more 🎉

Fundamentals

What is space complexity?

July 8, 2022

The efficiency of an algorithm doesn’t just end with seeing how much time it takes to run. There are others factors too, such as:

1. The amount of storage space taken by its variables.

2. The amount of traffic it generates on a network of computers.

3. The amount of data that must be moved to and from disks.


As mentioned in the previous post too, you analyze the time required for an algorithm and the space required by the data structures to decide the best solution for a problem. In this post we will talk about the space part. This is where space complexity comes in.



What is space complexity?

Space complexity is the amount of memory used by the algorithm, including the input values of the algorithm, to execute and produce the result.

An algorithm uses the memory in your computer for various things:

1. Variables (This includes the constant values and temporary values)

2. Program Instruction (This is the memory that the algorithm itself uses to store itself in the memory)

3. Execution (This is the memory used by the algorithm during its execution)


While executing an algorithm, there might be a case where some extra space or the temporary space is being used. This is called auxillary space. For example, if you are using a temporary variable to store initial values of a data structure, that counts as auxiliary space. But, if you are making changes in the original data structure itself, then the auxiliary space would be O(1).


Space complexity of an algorithm is the auxillary space + the input space.



Analysing the space complexity of an algorithm

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


Example 1

The above function requires 3 units of space for the parameters (x, y, z) and 1 for the local variable (r), and this never changes, irrespective of the input size. So the space complexity of this program is O(1).


Example 2

The above function requires N units for the array ‘a’, plus a space for n, r and i each. So the space complexity so it's O(N).



Hope this is helpful and gives you a basic idea on what space complexity is and how it is calculated 😌 You can send us a mail at hello@byteavenue.org or DM us on Instagram if you have any questions 💪

Want to learn more?

Our first course, Introduction to Data Structures in C++ worth ₹499/month is available at a price of your choice for the first month access.

Offer available for a limited time

Subscribe

Learn more

301/302, 3rd Floor, Saket Callipolis, Sarjapur Main Rd, Doddakannelli, Bengaluru, Karnataka 560035

© CodePark Pvt. Ltd. 2022

301/302, 3rd Floor, Saket Callipolis, Sarjapur Main Rd, Doddakannelli, Bengaluru, Karnataka 560035

© CodePark Pvt. Ltd. 2022

301/302, 3rd Floor, Saket Callipolis, Sarjapur Main Rd, Doddakannelli, Bengaluru, Karnataka 560035

© CodePark Pvt. Ltd. 2022