As mentioned in Exercise 5.38, repeated String concatenation can be expensive. Consequently, Java provides a StringBuilder class. A StringBuilder is somewhat like an ArrayList that stores unlimited characters. The StringBuilder allows one to easily add to the end, automatically expanding an internal character array (by doubling its capacity) as needed. In so doing, the cost of appending can be assumed to be proportional to the number of characters added to the StringBuilder (rather than the number of characters in the result). At any point, the StringBuilder can be used to construct a String. Figure 5.16 contains two methods that return Strings containing N xs. What is the running time of each method? Run the methods on various values of N to verify your answer.

Exercise 5.38

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.