What is space complexity of an algorithm and how it is measured?
Overview
In computer science, there are multiple ways to solve a problem, but to pick an efficient one, there are certain parameters which include time complexity and space complexity.
Space complexity
The space complexity is the measurement of total space required by an algorithm to execute properly. It also includes memory required by input variables. Basically, it's the sum of
Note: Space complexity
Auxiliary space Memory used by input variables
Space complexity is the parallel concept to time complexity. For example, if we want to initialize an array of
Notations for space complexity
If our algorithm takes a lot of memory to execute, then our compiler will not allow us to run it. To avoid compiler crashes, we need to compute the space complexity of our algorithm. There are many notations available to compute space complexity:
- Big-O notation :
- Omega Notation:
- Theta Notation:
Let's understand them briefly. But our focus would be on big-O notation, as it's widely used by developers:
Big-O notation
This big-O notation describes the asymptotic upper bound, the worst case of space complexity. Basically, it's the measure of the maximum amount of space our algorithm takes to grow with respect to the size of input data. The important big-O notations are as follows:
When the algorithm takes the same amount of space regardless of the input size
When the algorithm takes space proportional to the
When an algorithm takes space directly proportional to the input size
When the space complexity of an algorithm grows proportionally to the input size
When the space complexity grows proportionally to the square of the input size
Omega notation:
The omega notation describes the asymptotic lower bound. It is the best-case scenario in terms of time and space complexity. Actually, it's the minimum amount of space our algorithm takes to grow with respect to the input data.
Theta notation: θ
The theta notation means that the space complexity of an algorithm is between its upper-bound and lower-bound space complexity.
Measurement of space complexity
Most developers use big-O notation because it's relatively easy to estimate the maximum amount of space required. So we'll learn to measure the upper-bound of an algorithm in this section. Let's take an example of a function that returns the sum of the two variables.
#include <iostream>using namespace std;int sum(int a , int b) // Inter a and b{return a + b; // returning sum is integer too}int main() {// your code goes hereint x = 10;int y = 20;cout << "Sum of a & b =" << sum(x,y);return 0;}
Calculate space complexity
In this program, there are five variables allocated in the memory:
- The integer variables in the main function
x,y. - The integer variables in the sum function
a,b.. - The third integer, returning variable
sum.
A single variable uses
int sum(int arr[ ], int n) // n is the size of array arr{int arr_sum =0; // x takes 4 bits as integer variablefor (int i=0; i<n; i++) // i takes 4 bits as integer variable{arr_sum = arr_sum + arr[i];}return x;}
Calculate space complexity
In this program, there are five variables allocated in the memory:
- The array
arr[]is integer type with sizeso its space complexity is bits. - The integer variables in the
int n,int iandint sumwill takebytes individually, that is, bytes ( bytes).
The total memory this program takes (
Different Space for Variables in C/C++
Type | Size(bytes) |
bool, char, unsigned char, signed char, __int8 | 1 |
__int16, short, unsigned short, wchar_t, __wchar_t | 2 |
float, _int32, int, unsigned int, long, unsigned long | 4 |
double, __int64, long double, long long | 8 |
