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.

Common Operations §

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