**Space Complexity:**

**Auxiliary Space**is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size.

Space complexity includes both
Auxiliary space and space used by input.

Space complexity = Auxiliary space + space used by input

For example, if we want to compare standard sorting algorithms
on the basis of space, then Auxiliary Space would be better criteria than Space
Complexity.

Merge Sort uses O(n) auxiliary space (extra space), Insertion
sort and Heap Sort use O(1) auxiliary space. Space complexity of all these
sorting algorithms is O(n) though.

## No comments:

## Post a Comment