Does an algorithm's space complexity include input?

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)?

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).

StackExchange Computer Science Q#156949, answer score: 25