CSC300 / CSC402: XPerformanceOfStrings [12/13]

Note: Java's StringBuilder can be used instead of StringBuffer.

  public static String makeStringUsingConcat (int N) {
    String result = "";
    for (int i=0; i<N; i+=1) {
      result = result + "*";
    }
    return result;
  }

Output

********************************
Elapsed count f(          512):           131,328:      3.992 [     0.001 :      1.000]
Elapsed count f(        1,024):           524,800:      3.996 [     0.001 :      1.000]
Elapsed count f(        2,048):         2,098,176:      3.998 [     0.004 :      4.000]
Elapsed count f(        4,096):         8,390,656:      3.999 [     0.011 :      2.750]
Elapsed count f(        8,192):        33,558,528:      4.000 [     0.048 :      4.364]
Elapsed count f(       16,384):       134,225,920:      4.000 [     0.098 :      2.042]
Elapsed count f(       32,768):       536,887,296:      4.000 [     0.180 :      1.837]
Elapsed count f(       65,536):     2,147,516,416:      4.000 [     0.574 :      3.189]
Elapsed count f(      131,072):     8,590,000,128:      4.000 [     1.794 :      3.125]
Elapsed count f(      262,144):    34,359,869,440:      4.000 [     6.947 :      3.872]
Elapsed count f(      524,288):   137,439,215,616:      4.000 [    28.864 :      4.155]
Elapsed count f(    1,048,576):   549,756,338,176:      4.000 [   125.439 :      4.346]

N concatenations in quadratic time

Each concatenation is amortized linear time

A common bug in collections (how to print an array in quadratic time):

  public static String toString () {
    String result = "";
    for (int i=0; i<N; i+=1) {
      result = result + a[i];
    }
    return result;
  }