What is the time complexity of the add and element in a Java Array?

Question

Hello I am research about that, but I cannot found anything in the oracle website.

The question is the next.

If you are using an static Array like this

int[] foo = new int[10];

And you want add some value to the 4 position of this ways

foor[4] = 4;

That don't shift the elements of the array so the time complexity will be O(1) because if you array start at 0x000001, and have 10 spaces, and you want put some in the x position you can access by (x*sizeOf(int))+initialMemoryPosition (this is a pseudocode)

Is this right, is this the way of that this type of array works in java, and if its time complexity O(1)

Thanks

Answer 1

The question is based on a misconception: in Java, you can't add elements to an array.

An array gets allocated once, initially, with a predefined number of entries. It is not possible to change that number later on.

In other words:

int a[] = new int[5];
a[4] = 5;

doesn't add anything. It just sets a value in memory.

So, if at all, we could say that we have somehow "O(1)" for accessing an address in memory, as nothing related to arrays depends on the number of entries.

Note: if you ask about ArrayList, things are different, as here adding to the end of the array can cause the creation of a new, larger (underlying) array, and moving of data.

Answer 2

An array is somewhere in memory. You don’t have control where, and you should not care where it is. The array is initialized when using the new type[size] syntax is used.

Accessing the array is done using the [] index operator. It will never modify size or order. Just the indexed location if you assign to it.

See also https://www.w3schools.com/java/java_arrays.asp

The time complexity is already correctly commented on. But that is the concern after getting the syntax right.

An old post regarding time complexity of collections can be found here.

Answer 3

Yes, it takes O(1) time. When you initialize an array, lets say, int[] foo = new int[10], then it will create a new array with 0s. Since int has 4 bytes, which is 32 bits, every time assign a value to one element, i.e., foo[4] = 5, it will do foo[32 x input(which is 4)] = value(5); That's why array is 0-indexed, and how they assign values in O(1) time.