---

Space Complexity

---

Performance analysis of an algorithm is the process of calculating space and time required by that algorithm.
Space required to complete the task of that algorithm (Space Complexity).
Time required to complete the task of that algorithm (Time Complexity)

Space Complexity

Definition

The space complexity of an algorithm is the amount of memory it needs to execute and produce the result.

For any algorithm memory may be used for the following:

Variables (This include the constant values, temporary values)
Program Instruction
Execution

Instruction space: Instruction space is the space needed to store the compiled version of the program instructions.

Data space: Data space is the space needed to store all constant and variable values. Data space has two components:

• Space needed by constants and simple variables in program.
• Space needed by dynamically allocated objects such as arrays and class instances.

Environment stack space: The environment stack is used to save information needed to resume execution of partially completed functions.

Note: But while calculating the Space Complexity of any algorithm, we usually consider only Data Space and we neglect the Instruction Space and Environmental Stack.

The Space needed by each of these algorithms is seen to be the sum of the following component.

1.A fixed part that is independent of the characteristics (eg:number,size) of the inputs and outputs. The part typically includes the instruction space (ie. Space for the code), space for simple variable and fixed-size component variables (also called aggregate) space for constants, and so on. It is also known as Constant space complexity

2. A variable part that consists of the space needed by component variables whose size is dependent on the particular problem instance being solved, the space needed by referenced variables (to the extent that is depends on instance characteristics), and the recursion stack space. It is also known as Linear space complexity

The space requirement s(p) of any algorithm p may therefore be written as,
S(P) = c+ Sp(Instance characteristics)
Where ‘c’ is a constant.

Example of Constant Space Complexity

Algorithm abc(a,b,c)
{
	return a + b * c + (a+b-c) / (a+b) + 4.0;
}

The problem instance is characterized by the specific values of a,b, and c. Making the assumption that one word is adequated to store the values of each of a,b,c and the result, so word count is constant that is 3. There is no dependent Instance characteristics so Sp=0.
S(P) = 3+0 = 3

Example of Linear Space Complexity

Algorithm sum(a,n)
{
	s:=0;
	for i:=1 to n do
		s:= s+a[i];
	return s;
}

The problem instance is characterized by the specific values of n, s and i, c is 3. The space needed by a is at least n words, since a must be large enough to hold the n elements to be summed, Sp is n.
S(P) = n+3

---

Next Topic :Time Complexity