Space Complexity

Space complexity analyses the amount of storage or ‘space’ used by the algorithm, in relation to the input size.

Auxiliary space is the space required not including the input i.e. the space taken up by the algorithm itself

Normal function calls don’t take up additional space, because the space is reallocated after the function terminates. However, recursive function calls will use additional space as many function calls are initialised at once.

If a variable is passed as an argument, no additional space is required.

Examples §

Command	Space complexity
Initializing, Assigning a variable	$O(1)$ constant
Storing an array/list/stack/queue	$O(n)$ linear
Iterative Function Calls	$O(1)$ constant
Recursive Function Calls	$O(n)$ linear