php |
What is the difference between Auxiliary space and space complexity?
Auxiliary space is temporary or extra space used by an algorithm. This temporary space allocated in order to solve the problem.
Space complexity is total space taken by the algorithm with respect to the input size. Space complexity includes both auxiliary space and space taken by input size.
For examples: Merge sort uses new array to solve the problem so it has auxiliary space complexity of O(n), whereas the Quick sort is in place sorting algorithm and does not use any extra space so it has auxiliary space of O(1).