2
$\begingroup$

The auxiliary space analysis that involves modifying the input array can lead to "unfair" situations. Examples:

Consider that an algorithm that uses O(N) memory and does not need to continuously read the input space can choose to move its allocation into the input space and thereby appear O(1) regardless of the algorithm itself.
Or, consider if extra space were passed in the form of a redundant variable or unused sign bits, the algorithm could masquerade as O(1) again even though nothing changed about the core algorithm or the input information.

Considering auxiliary space complexity formally requires an immutable input tape, I believe the best approach is to consider the corresponding problem that considers the input immutable; that requires extra space declared explicitly.

Lots of leetcode solutions falsely masquerading as O(1) auxiliary space.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Depending on the context, it's common to treat the input as read-only when analyzing auxiliary space.

A separate notion is that of an in-place algorithm. In an in-place algorithm, we treat the input as writeable, and count the amount of extra space beyond that.

If the context is not clear, I suggest that you specify explicitly whether you treat the input as writeable or not.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That context is mainly "is it inplace"? I wouldn't consider bubble sort O(N) extra space. $\endgroup$ Commented Jun 24, 2024 at 4:21
  • $\begingroup$ @SimonWalker, see revised answer. $\endgroup$ Commented Jun 24, 2024 at 16:28
-1
$\begingroup$

A modification of the input format/argument changes the problem itself. This change is usually just formal, but sometimes it could be essential.

In computational complexity analysis we talk about information quantity rather than input size. For example in Subset Sum problem switching to unary numeral system allows to design a simple algorithm based on dynamic programming method with running time bounded by the square of the input size. While for binary or decimal notation system used in input nobody knows an algorithm with running time bounded by a subexponential function of the input size. And since the information quantity doesn't depend on notation system, we don't speak about polynomial solvability of this problem in spite of that a polynomial algorithm exists for the case of unary notation in input.

If you analyze space complexity of a certain function you may (in some cases) reduce auxiliary space complexity by using unnecessary input space. Or you may use even necessary space if you don't lose data, as it is done in in-place merge sort. And changing the input to have such an extra space is an easy way to reduce auxiliary space. Note that this reduction may be essential or just formal, too, if the total amount of memory doesn't change.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.