Question

The ArrayList class contains a trim method that resizes the internal array to exactly the capacity. The trim method is intended to be used after all the items have been added the ArrayList, in order to avoid wasting space. Suppose, however, the novice programmer invokes trim after each add. In that case, what is the running time of building an N-item ArrayList? Write a program that performs 100,000 adds to an ArrayList and illustrates the novice’s error.

Answer 1

Answer:

public void trimToSize() {

modCount++;

if (size < elementData.length) {

elementData = (size == 0)

? EMPTY_ELEMENTDATA

: Arrays.copyOf(elementData, size);

}

}

Now, the running time for copyOf() function is O(N) where N is the size/capacity of the ArrayList. Hence, the time complexity of trimToSize() function is O(N).

Hence, the running time of building an N-item ArrayList is O(N^2).

Please find the sample code below.

CODE

==================

import java.util.ArrayList;

public class Driver {

  public static void main(String[] args) throws Exception{

      int N = 100000;

      ArrayList<Integer> arr = new ArrayList<>(N);

     

      long startTime = System.currentTimeMillis();

      for(int i=0; i<N; i++) {

          arr.add(i);

          arr.trimToSize();

      }

      long endTime = System.currentTimeMillis();

      double time = (endTime - startTime)/1000;

      System.out.println("Total time taken = " + time + " seconds.");

  }

}

Explanation: