1

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?

Irongrave
  • 553
  • 1
  • 5
  • 15

2 Answers2

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?

Community
  • 1
  • 1
Natecat
  • 2,175
  • 1
  • 17
  • 20
1

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

  1. if initialCapacity>0, elementData = new Object[initialCapacity];

  2. if initialCapacity==0, elementData = EMPTY_ELEMENTDATA;

  3. 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. :)

Debosmit Ray
  • 5,228
  • 2
  • 27
  • 43