Java ArrayList constructor time complexity

Question

I'm doing some research into the ArrayList class as part of a school project.

In the Java API docs at Oracle's site, it mentions that all operations except a given few are "roughly linear time."

The constructors are not listed as part of the given few, but I'm having a hard time seeing how this:

public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       }
}

is linear time. Am I missing something here?

In addition, the constructor is called once during the lifecycle of a given ArrayList, so the constructor might not be considered as part of the overall running time. — Tim Biegeleisen
– Tim Biegeleisen, Commented Mar 30, 2016 at 1:16

Community · Accepted Answer · 2017-05-23 12:31:38Z

3

It's linear because array declaration is O(n), as given in this question: Java: what's the big-O time of declaring an array of size n?

edited May 23, 2017 at 12:31

CommunityBot

11 silver badge

answered Mar 30, 2016 at 1:17

Natecat

2,1931 gold badge17 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Debosmit Ray · Accepted Answer · 2016-03-30 01:22:59Z

1

In the code you have posted, one of 3 things happen.

if initialCapacity>0, elementData = new Object[initialCapacity];
if initialCapacity==0, elementData = EMPTY_ELEMENTDATA;
if initialCapacity<0, throw an exception.

All of these operations, except for number 1, take constant time, since no iteration over a collection is required.

Number 1 takes linear time because declaring an array of size n takes O(n) time. I will not re-write the entire reason, since there is a post on SO covering this somewhere. A general idea: this occurs because space has to be allocated for each of the n items.

I hope to have been of help. :)

edited Mar 30, 2016 at 1:22

answered Mar 30, 2016 at 1:20

Debosmit Ray

5,4332 gold badges31 silver badges44 bronze badges

3 Comments

Natecat Over a year ago

I think you mean number 1

Debosmit Ray Over a year ago

@Natecat Haha sorry :p

Debosmit Ray Over a year ago

@Natecat's answer shows the link. But, here it is anyway.

Collectives™ on Stack Overflow

Java ArrayList constructor time complexity

2 Answers 2

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related