gotchaMinor
Difference between auxiliary space v/s space complexity
Viewed 0 times
spacedifferencebetweencomplexityauxiliary
Problem
I'm confused between these two terms as for example - the Auxiliary space of merge sort, heapsort and insertion sort is $O(1)$ whereas Space complexity of merge sort, insertion sort, heapsort is $O(n)$.
So, if someone asks me what's the Space complexity of merge sort, heapsort or insertion sort then what should I tell them $O(1)$ or $O(n)$?
Also, note in case of selection sort, I've read it's Space Complexity is $O(1)$ which is auxiliary space.
So, if someone asks me what's the Space complexity of merge sort, heapsort or insertion sort then what should I tell them $O(1)$ or $O(n)$?
Also, note in case of selection sort, I've read it's Space Complexity is $O(1)$ which is auxiliary space.
Solution
First consider the definitions below:
$\mathbf{Auxiliary\space Space}$ is the temporary space allocated by your algorithm to solve the problem, with respect to input size.
$\mathbf{Space \space Complexity}$ is the total space used by your algorithm to solve the problem, with respect to input size. Note that the Space Complexity $\textit{includes}$ input size.
I can see where your confusion comes from; usually, when we say "Space complexity of Mergesort" we mean its Auxiliary Space, because we obviously cannot improve the space we use for the input itself. As such, some of the statements in your question are not correct.
$\bullet$ Mergesort has Auxiliary space of $O(n)$ (in its common use) since you allocate a new array, and Space complexity of $O(n)$
An example between the two would be:
If we compare Quicksort and Mergesort, they both have a space complexity of $O(n)$ and run at $O(n\log n)$ time, but Mergesort requires Auxiliary space of $O(n)$ while Quicksort requires Auxiliary space of $O(1)$
Finally, to answer your question: usually the intention while asking about "space complexity" is indeed Auxiliary space, although there is some ambiguity here in regard to the formal definitions above. To be pedantic, you can separate the two space complexity types in your answer.
$\mathbf{Auxiliary\space Space}$ is the temporary space allocated by your algorithm to solve the problem, with respect to input size.
$\mathbf{Space \space Complexity}$ is the total space used by your algorithm to solve the problem, with respect to input size. Note that the Space Complexity $\textit{includes}$ input size.
I can see where your confusion comes from; usually, when we say "Space complexity of Mergesort" we mean its Auxiliary Space, because we obviously cannot improve the space we use for the input itself. As such, some of the statements in your question are not correct.
$\bullet$ Mergesort has Auxiliary space of $O(n)$ (in its common use) since you allocate a new array, and Space complexity of $O(n)$
An example between the two would be:
If we compare Quicksort and Mergesort, they both have a space complexity of $O(n)$ and run at $O(n\log n)$ time, but Mergesort requires Auxiliary space of $O(n)$ while Quicksort requires Auxiliary space of $O(1)$
Finally, to answer your question: usually the intention while asking about "space complexity" is indeed Auxiliary space, although there is some ambiguity here in regard to the formal definitions above. To be pedantic, you can separate the two space complexity types in your answer.
Context
StackExchange Computer Science Q#108505, answer score: 7
Revisions (0)
No revisions yet.