CODEWITHSUNDEEP
javatime-complexity
FabolousPotato
FabolousPotato

Reputation: 65

Time complexity of initializing an arraylist

What is the time complexity of initializing an arraylist?

Arraylist<E> A = new Arraylist<E>

What about:

Arraylist<Integer> B = new ArrayList<>(Arrays.asList(1,2,3,4,5)

For the first option, I believe it would be O(1) constant time. However the second option is what I have trouble thinking about.

Upvotes: 0

Views: 2313

Answers (1)

Eugene
Eugene

Reputation: 120858

Arrays.asList - just this one would be O(1). Under the hood a new ArrayList is created with the given array - no matter of the size of the array.

Or simpler, the same action happens all the time no matter the size of the array = it's constant.

When you do new ArrayList(Arrays.asList...), internally it copies the data:

....
elementData = Arrays.copyOf(elementData, size, Object[].class);

that will ultimately call System::arrayCopy; and this is where it gets tricky. In general, that could be thought as O(n), but since that is a native method is could be implemented as a single CPU instruction; thus becoming O(1).

I would still go with O(n) as the answer.

Upvotes: 2

Related Questions