Is fixed array size O(n) or O(1) in space?

Question

Is an array declared like this:
int array[M], O(1) in space or O(n)? where M is some fixed value. To me O(n) makes sense because it is not just a single variable but an entire array. But then i think it could be O(1) since we have a fixed size and it is not changing!

Answer 1

If your array is of a fixed size and it does not vary with the size of the input it is O(1) since it can be expressed as c * O(1) = O(1), with c being some constant. An example would be if you needed an array of size 5 to hold state in your algorithm that runs over a million (or some other arbitrary number) integers. The important thing is M and N are independent.

If however M represents the size of your input or a value that is directly dependent of the input size (i.e. N/2 or some other linear function), then really M grows along with your N, the input size so it would be O(N). An example would be an array that holds all input numbers of which you want to run an algorithm over (i.e determining the sum of the squares).

Answer 2

I would say O(1) when M is a constant. If it is O(n) its size must be linear function of M, which in this case is not.

Answer 3

The other answers you were given are correct, formally it's O(1).

But think very carefully about the meaning of "constant". The O(...) notation is not meant to measure the performance of an actual computer program, but to categorize algorithms by complexity.

If you are implementing an algorithm that works on an array of objects reading each of them only once (for example), you may say "ok, let's fix the number of elements to N", but that won't move the algorithm into the O(1) complexity class, the algorithm is still O(n) but you're limiting your test cases to n = N where N is fixed.