1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.