arrayscspace-complexity

Space Complexity Query


When I create an array, lets say that it is fixed in size throughout the program execution, then will the space complexity by O(n) or O(1)? I ask this question because during the program execution I am using a constant amount of memory so the space complexity should be O(1) but why is it considered O(n)?

I think that the space complexity should be O(1) if the array doesn't grow in size and not O(n).


Solution

  • Formally, if it does not vary with input size, your fixed array should be considered O(1).

    There are actually a couple of things to consider here. First one being that inputs are not counted towards the space complexity, only the structures you create as part of the function(s). If your array is an input to the function then it will be O(1). The second thing is actually how the array length relates to your N and Ms - does it grow with them ? If it remains fixed, as you said, then it's O(1) again, if your array has to change length based on other input sizes then it's no longer constant - at this point you should start considering it as a variable length.

    Basically, to be O(1) it should be an input or if it's not - it should truly be a constant and its length should be unrelated to other lengths.