11
$\begingroup$

Consider the Kadane's algorithm for finding maximum subarray within an array:

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""

    best_sum = 0
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

The algorithm requires constant space to execute, apparently. But still, it accepts a list of n elements as input. So is its space complexity O(n) or O(1)?

Improve this question
$\endgroup$
2
  • 7
    $\begingroup$ This algorithm looks like it's "online", needing only one element of the sequence at the time. It doesn't require the whole sequence to exist for the duration of the algorithm so the space complexity of an input can be as low as O(1). $\endgroup$
    – Emperor Orionii
    Jan 20 at 8:58
  • $\begingroup$ As footnote 40 here notes, $\mathsf{LOGSPACE}$ only makes sense because its input, thought of as on a read-only tape, isn't counted. If, on the other hand, you edit an input in-place (as does e.g. Python's random.shuffle), this argument for not counting it breaks down. $\endgroup$
    – J.G.
    Jan 22 at 10:24

5 Answers 5

Reset to default
25
$\begingroup$

It depends on the chosen convention. I often prefer the convention that considers that the input is not part of the space complexity, for different reasons:

  • the space complexity of a function answer the question "do I have enough memory to finish my computation?". In that aspect, I consider that when calling a function, its argument is already written somewhere in the memory, and therefore there is no need to consider it for the future computation (we already know that there is enough space for the input).
  • the complexity classes L and NL (problems that can be solved deterministically and non-deterministically respectively in logarithmic space) make no sense if you consider the input as part of the space complexity (otherwise any space complexity would always be at least linear).
Improve this answer
$\endgroup$
3
  • 10
    $\begingroup$ A third reason to prefer that convention is that it allows giving strictly more information than the other convention. If the space complexity is more than linear, then the choice of convention doesn't matter when using big-oh notation. If the space complexity is less than linear, then with one convention you can only say "the space complexity is linear" whereas with the other convention you can be more specific (such as giving class L and NL). $\endgroup$
    – Stef
    Jan 20 at 17:22
  • $\begingroup$ You can also opt or not to count the output size. In your example, you could have an asynchronous function that produces output elements one by one, in that case the output might be consumed (and freed) by other parts of the program while your function computes it. If however your function returns a "whole list/array" then the output size matters for sure. $\endgroup$
    – Bakuriu
    Jan 21 at 11:01
  • 2
    $\begingroup$ There is a downside to the approach of not counting "input size", though, it loses the distinction between streaming and non-streaming algorithms. For example, while a good sort implementation only uses O(log N) auxiliary space, it needs the full O(N) input to be available at once, while Kadane's algorithm here uses O(1) auxiliary space and O(1) input space, and thus can work on a stream. $\endgroup$
    – Matthieu M.
    Jan 21 at 12:46
6
$\begingroup$

Auxiliary Space: The extra space that is taken by an algorithm temporarily to finish its work

Space Complexity: Space complexity is the total space taken by the algorithm with respect to the input size plus the auxiliary space that the algorithm uses.

Referred from here

i.e., space complexity of a program on the whole also includes the space taken up by the input values. Space Complexity = Auxiliary space + Space used up by input values.

But when we compare two algorithms that have the same end goal with similar input types, often the space taken up by the input is disregarded. Only the auxiliary space of the algorithm is considered.

Hence it is said that Kadane's algorithm runs in constant space i.e. O(1)

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Is that your opinion or is there an unnamed source from which you quoted this definition? It doesn't seem particularly standard to me. $\endgroup$
    – Stef
    Jan 20 at 11:42
  • 2
    $\begingroup$ What/whom are you quoting? $\endgroup$
    – Bergi
    Jan 20 at 11:46
  • 2
    $\begingroup$ Please edit the answer based on feedback. Don't just add information in the comments -- we want answers to stand on their own, without people needing to read the comments. We expect you to provide proper attribution to all material originally written by others: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W. ♦
    Jan 20 at 19:08
4
$\begingroup$

No, the input does not count in the space complexity. The data has to be supplied anyway and if we counted it, no $o(n)$ complexity (in particular $O(1)$) would be possible.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ This seems to contradict with the definition from Wikipedia (and some other resources), where the space other than that consumed by the input is called auxiliary space. $\endgroup$
    – Eugene Yarmash
    Jan 19 at 15:29
  • 4
    $\begingroup$ @EugeneYarmash Everything before the mention of 'auxiliary space' in the Wikipedia article talks about space complexity 'with regard to input size' — and in fact refers to LOGSPACE, which as noted could not exist were input counted as part of the complexity. That page should probably have a formal definition of space complexity, and I would argue that the section on 'auxiliary space complexity' needs at the very least a clarification that this is how the topic is sometimes referred to in the 'working world' of computer algorithms but that it's definitely not a theoretical CS term. $\endgroup$
    – Steven Stadnicki
    Jan 20 at 17:04
1
$\begingroup$

Complexity analysis is usually done to compare algorithms that process the same input. In this case, it makes little sense to include the space of the input data, because it's the same for all algorithms being compared and doesn't affect the comparison.

However, we might want to compare algorithms that process different forms of input, e.g. arrays versus linked lists. In this case, the space used by the input is a function of the algorithm, so we should include the input space.

Improve this answer
$\endgroup$
0
$\begingroup$

While the question has been mostly answered by other people, I want to make a note that in the algorithm described, you have to keep track of the index you are at to iterate to the next array element. This index tracker, at last position, grows as input grows, so it is not quite O(1) in terms of space, but O(lg(n)) (since you can keep the binary representation of the index).

Although, again, saying O(1) is convention in some places.

Improve this answer
$\endgroup$
1
  • $\begingroup$ (In the conventional RAM model, each memory cell can hold an integer a convenient fixed multiple of the size needed to represent n.) $\endgroup$
    – greybeard
    Oct 27 at 10:55

Your Answer

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

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