Space Complexity of an array?

java space-complexity
Ritesh picture Ritesh · Jun 8, 2017 · Viewed 14.3k times · Source

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

Jeremy Grand picture Jeremy Grand · Jun 8, 2017

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)

Related questions

Will Arrays.sort() increase time complexity and space time complexity?

There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1). If I use Arrays.sort(arr), and use a for loop to one pass loop, for example: public static int …

Read More
Why does QuickSort use O(log(n)) extra space?

I have implemented the below quicksort algorithm. Online I've read that it has a space requirement of O(log(n)). Why is this the case? I'm not creating any extra data structures. Is it because my recursion will use some …

Read More
Bloom Filter Implementation

Using Bloom filter, we will be getting space optimization. The cassandra framework also has an implementation of Bloom Filter. But in detail, how is this space optimization achieved?

Read More