Space Complexity of an array?

Question

I have an array of size N, and N is <=200.

What would be the space complexity here.

O(1) or (N) - considering the constraint N.

Answer 1

Complexity is only relevant when you try to foresee the performances of your algorithm with various input. I don't think it has any meaning to just speak about the space-complexity of an array without any context.

If you'll always create an array of size N (hard-coded), it's O(1), because no matter what input your algorithm crunches, the space taken by your array is the same.

If your N grows with the size of the input, it's O(f(n)), where f(n) is the relation between n (size of input) and N (size of array).

NOTE : the formulation O(...) is a mathematical symbol to represent magnitude without any regard to the multiplier (sorry for the lack of precision, I'm way over my math degree and never learned the english terms), so, if N is a constant, O(N) = O(1) (they have the exact same meaning).

And if I'm remembering it right, if f < C * g , O(f) = O(g). Thus, if N is < 200 , O(N) = O(200) = O(1)

Answer 2

Space complexity is usually only defined for Algorithms.

But let's be crafty and form an algorithm from your Question.

Input: N values, N <= 200
Algorithm: Store all values
Output: None

Space complexity is the amount of memory you need to execute the algorithm, in relation to N.

When you store 1 number, you'll need one memory area. When you store 2 it doubles... Your memory complexity is O(n) which means it grows linearly; Just like it would be for this algorithm:

Input: N values, N <= 18,446,744,073,709,551,616 (unsigned int 64).
Algorithm: Store all values
Output: None

But 200 is a really small number, can't we just say O(1)?

Let's get crafty again, because we can make this O(1):

Input: N values, N <= 200
Algorithm: Store all values in an array of size 200
Output: None

When you store 1 number you will need 200 memory areas. When you store 2 numbers you will need 200 memory areas. When you store 200 numbers you will need 200 memory areas. This means the memory is constant and independent from N. Thus the complexity is O(1).

It's important to note that O(1) doesn't mean the amount of memory you need is 1, it means that the amount of memory you need is not in any relation to N. And thus it doesn't grow when N grows.

But what if my objects are 50GB Blu-ray Discs? O(1) should be very small but now it would be 10 Terabytes!

At this point we may finally realize that we don't always need to use Big O notations. We could just say that we need to store 10 Terabyte of Data and buy some Hard Disks. If your Teacher makes a fuss about whether you write O(1) for very small N or O(n), then he is a very bad teacher. The answer to this Question is neither going to change your life nor your career. Big O Notation only makes sense for numbers that can grow incredible large.