CSC300 / CSC402: Resizing Arrays and Amortized Analysis

Contents [0/13]

Amortized Analysis [1/13]
XPerformanceOfArrays [2/13]
XPerformanceOfArrays +1 [3/13]
XPerformanceOfArrays +10 [4/13]
XPerformanceOfArrays +100 [5/13]
XPerformanceOfArrays *2 [6/13]
XPerformanceOfArrays *4 [7/13]
XPerformanceOfArrays *8 [8/13]
XPerformanceOfArrays *1.5 [9/13]
XPerformanceOfArrays *1.1 [10/13]
XPerformanceOfStrings [11/13]
XPerformanceOfStrings [12/13]
XPerformanceOfStrings [13/13]

(Click here for one slide per page)


Amortized Analysis [1/13]

Algorithm input includes data and a sequence of operations performed by the client

Amortized analysis provides a worst-case performance guarantee on a sequence of operations

We will look at

XPerformanceOfArrays [2/13]

file:XPerformanceOfArrays.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
package algs14;
import stdlib.*;

public class XPerformanceOfArrays {
  private double[] a;
  private int N;
  public XPerformanceOfArrays() {
    this.a = new double[1];
    this.N = 0;
  }
  private void resize(int capacity) {
    double[] temp = new double[capacity];
    for (int i = 0; i < N; i+=1) {
      if (SHOW) StdOut.format ("%02d ", i);
      temp[i] = a[i];
      ops += 1;
    }
    if (SHOW) StdOut.println();
    a = temp;
  }
  public void push(double item) {
    if (N == a.length) resize (1+N); //resize((int)Math.ceil (N*1.5));
    a[N] = item;
    N += 1;
    ops += 1;
  }
  
  private static long ops;
  private static boolean SHOW = true;
  public static void main(String[] args) {
    timeTrial(32);
    SHOW = false;
    
    int MIN = 256; 
    int MAX = 100_000_000;
    double prevTime = timeTrial(MIN);
    double prevOps = ops;
    double deltaSum = 0;
    int deltaNum = 0;
    for (int N = MIN*2; N<=MAX; N += N) {
      double time = timeTrial(N);
      StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, ops, ops / prevOps, time, time/prevTime);
      prevTime = time;
      deltaSum += ops/prevOps;
      deltaNum += 1;
      prevOps = ops;
    }
    StdOut.format ("Average delta: %.3f\n", deltaSum/deltaNum);
  }
  public static double timeTrial(int N) {
    ops = 0;
    Stopwatch s = new Stopwatch();
    XPerformanceOfArrays stack = new XPerformanceOfArrays();
    for (int j=0; j<N; j+=1) {
      stack.push (j);
    }
    return s.elapsedTime();
  }
}

XPerformanceOfArrays +1 [3/13]

01
02
03
04
05
 
  public void push(double item) {
    if (N == a.length) resize(1+N);
    a[N] = item;
    N += 1;
  }

Output 

00 
00 01 
00 01 02 
00 01 02 03 
00 01 02 03 04 
00 01 02 03 04 05 
00 01 02 03 04 05 06 
00 01 02 03 04 05 06 07 
00 01 02 03 04 05 06 07 08 
00 01 02 03 04 05 06 07 08 09 
00 01 02 03 04 05 06 07 08 09 10 
00 01 02 03 04 05 06 07 08 09 10 11 
00 01 02 03 04 05 06 07 08 09 10 11 12 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
Elapsed count f(          512):           131,328:      3.992 [     0.005 :      2.500]
Elapsed count f(        1,024):           524,800:      3.996 [     0.010 :      2.000]
Elapsed count f(        2,048):         2,098,176:      3.998 [     0.008 :      0.800]
Elapsed count f(        4,096):         8,390,656:      3.999 [     0.060 :      7.500]
Elapsed count f(        8,192):        33,558,528:      4.000 [     0.088 :      1.467]
Elapsed count f(       16,384):       134,225,920:      4.000 [     0.182 :      2.068]
Elapsed count f(       32,768):       536,887,296:      4.000 [     0.685 :      3.764]
Elapsed count f(       65,536):     2,147,516,416:      4.000 [     2.292 :      3.346]
Elapsed count f(      131,072):     8,590,000,128:      4.000 [     8.996 :      3.925]
Elapsed count f(      262,144):    34,359,869,440:      4.000 [    38.306 :      4.258]

N pushes in quadratic time

Each push is amortized linear time

XPerformanceOfArrays +10 [4/13]

01
02
03
04
05
 
  public void push(double item) {
    if (N == a.length) resize(10+N);
    a[N] = item;
    N += 1;
  }

Output 


00 
00 01 02 03 04 05 06 07 08 09 10 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
Elapsed count f(          512):            13,824:      3.914 [     0.001 :   Infinity]
Elapsed count f(        1,024):            53,657:      3.881 [     0.003 :      3.000]
Elapsed count f(        2,048):           211,353:      3.939 [     0.003 :      1.000]
Elapsed count f(        4,096):           842,956:      3.988 [     0.011 :      3.667]
Elapsed count f(        8,192):         3,366,912:      3.994 [     0.011 :      1.000]
Elapsed count f(       16,384):        13,441,433:      3.992 [     0.063 :      5.727]
Elapsed count f(       32,768):        53,713,305:      3.996 [     0.085 :      1.349]
Elapsed count f(       65,536):       214,813,900:      3.999 [     0.348 :      4.094]
Elapsed count f(      131,072):       859,176,960:      4.000 [     1.005 :      2.888]
Elapsed count f(      262,144):     3,436,288,409:      4.000 [     3.955 :      3.935]
Elapsed count f(      524,288):    13,744,314,777:      4.000 [    17.241 :      4.359]
Elapsed count f(    1,048,576):    54,976,629,964:      4.000 [    71.803 :      4.165]

N pushes in quadratic time

Out of 10 pushes: 9 are constant time; 1 is linear

Each push is amortized linear time

XPerformanceOfArrays +100 [5/13]

01
02
03
04
05
 
  public void push(double item) {
    if (N == a.length) resize(100+N);
    a[N] = item;
    N += 1;
  }

Output 


00


        
Elapsed count f(          512):             2,018:      3.610 [     0.000 :      0.000]
Elapsed count f(        1,024):             6,535:      3.238 [     0.000 :        NaN]
Elapsed count f(        2,048):            23,069:      3.530 [     0.001 :   Infinity]
Elapsed count f(        4,096):            86,137:      3.734 [     0.006 :      6.000]
Elapsed count f(        8,192):           340,374:      3.952 [     0.008 :      1.333]
Elapsed count f(       16,384):         1,353,148:      3.975 [     0.013 :      1.625]
Elapsed count f(       32,768):         5,395,896:      3.988 [     0.019 :      1.462]
Elapsed count f(       65,536):        21,550,192:      3.994 [     0.072 :      3.789]
Elapsed count f(      131,072):        86,002,883:      3.991 [     0.162 :      2.250]
Elapsed count f(      262,144):       343,877,866:      3.998 [     0.553 :      3.414]
Elapsed count f(      524,288):     1,374,719,831:      3.998 [     1.775 :      3.210]
Elapsed count f(    1,048,576):     5,498,344,562:      4.000 [     7.048 :      3.971]
Elapsed count f(    2,097,152):    21,992,308,724:      4.000 [    29.507 :      4.187]

N pushes in quadratic time

Out of 100 pushes: 99 are constant time; 1 is linear

Each push is amortized linear time

XPerformanceOfArrays *2 [6/13]

01
02
03
04
05
 
  public void push(double item) {
    if (N == a.length) resize(2*N);
    a[N] = item;
    N += 1;
  }

Output 

00 
00 01 
00 01 02 03 
00 01 02 03 04 05 06 07 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 
Elapsed count f(          512):             1,023:      2.002 [     0.000 :        NaN]
Elapsed count f(        1,024):             2,047:      2.001 [     0.000 :        NaN]
Elapsed count f(        2,048):             4,095:      2.000 [     0.000 :        NaN]
Elapsed count f(        4,096):             8,191:      2.000 [     0.000 :        NaN]
Elapsed count f(        8,192):            16,383:      2.000 [     0.000 :        NaN]
Elapsed count f(       16,384):            32,767:      2.000 [     0.001 :   Infinity]
Elapsed count f(       32,768):            65,535:      2.000 [     0.003 :      3.000]
Elapsed count f(       65,536):           131,071:      2.000 [     0.007 :      2.333]
Elapsed count f(      131,072):           262,143:      2.000 [     0.002 :      0.286]
Elapsed count f(      262,144):           524,287:      2.000 [     0.003 :      1.500]
Elapsed count f(      524,288):         1,048,575:      2.000 [     0.007 :      2.333]
Elapsed count f(    1,048,576):         2,097,151:      2.000 [     0.015 :      2.143]
Elapsed count f(    2,097,152):         4,194,303:      2.000 [     0.028 :      1.867]
Elapsed count f(    4,194,304):         8,388,607:      2.000 [     0.043 :      1.536]
Elapsed count f(    8,388,608):        16,777,215:      2.000 [     0.055 :      1.279]
Elapsed count f(   16,777,216):        33,554,431:      2.000 [     0.147 :      2.673]
Elapsed count f(   33,554,432):        67,108,863:      2.000 [     0.360 :      2.449]
Elapsed count f(   67,108,864):       134,217,727:      2.000 [     0.597 :      1.658]
Average delta: 2.000

N pushes in linear time

Each time we resize: constant pushes double

Each push is amortized constant time

XPerformanceOfArrays *4 [7/13]

01
02
03
04
05
 
  public void push(double item) {
    if (N == a.length) resize(4*N);
    a[N] = item;
    N += 1;
  }

Output 



00 
00 01 02 03 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 
Elapsed count f(          512):               853:      2.501 [     0.000 :        NaN]
Elapsed count f(        1,024):             1,365:      1.600 [     0.000 :        NaN]
Elapsed count f(        2,048):             3,413:      2.500 [     0.000 :        NaN]
Elapsed count f(        4,096):             5,461:      1.600 [     0.000 :        NaN]
Elapsed count f(        8,192):            13,653:      2.500 [     0.001 :   Infinity]
Elapsed count f(       16,384):            21,845:      1.600 [     0.001 :      1.000]
Elapsed count f(       32,768):            54,613:      2.500 [     0.002 :      2.000]
Elapsed count f(       65,536):            87,381:      1.600 [     0.003 :      1.500]
Elapsed count f(      131,072):           218,453:      2.500 [     0.007 :      2.333]
Elapsed count f(      262,144):           349,525:      1.600 [     0.006 :      0.857]
Elapsed count f(      524,288):           873,813:      2.500 [     0.008 :      1.333]
Elapsed count f(    1,048,576):         1,398,101:      1.600 [     0.010 :      1.250]
Elapsed count f(    2,097,152):         3,495,253:      2.500 [     0.037 :      3.700]
Elapsed count f(    4,194,304):         5,592,405:      1.600 [     0.029 :      0.784]
Elapsed count f(    8,388,608):        13,981,013:      2.500 [     0.100 :      3.448]
Elapsed count f(   16,777,216):        22,369,621:      1.600 [     0.061 :      0.610]
Elapsed count f(   33,554,432):        55,924,053:      2.500 [     0.429 :      7.033]
Elapsed count f(   67,108,864):        89,478,485:      1.600 [     0.288 :      0.671]
Average delta: 2.050

N pushes in linear time

Each time we resize: constant pushes quadruple

Each push is amortized constant time

XPerformanceOfArrays *8 [8/13]

01
02
03
04
05
 
  public void push(double item) {
    if (N == a.length) resize(8*N);
    a[N] = item;
    N += 1;
  }

Output 




00 
00 01 02 03 04 05 06 07 
Elapsed count f(          512):               585:      1.778 [     0.000 :        NaN]
Elapsed count f(        1,024):             1,609:      2.750 [     0.000 :        NaN]
Elapsed count f(        2,048):             2,633:      1.636 [     0.000 :        NaN]
Elapsed count f(        4,096):             4,681:      1.778 [     0.000 :        NaN]
Elapsed count f(        8,192):            12,873:      2.750 [     0.001 :   Infinity]
Elapsed count f(       16,384):            21,065:      1.636 [     0.001 :      1.000]
Elapsed count f(       32,768):            37,449:      1.778 [     0.001 :      1.000]
Elapsed count f(       65,536):           102,985:      2.750 [     0.006 :      6.000]
Elapsed count f(      131,072):           168,521:      1.636 [     0.005 :      0.833]
Elapsed count f(      262,144):           299,593:      1.778 [     0.007 :      1.400]
Elapsed count f(      524,288):           823,881:      2.750 [     0.013 :      1.857]
Elapsed count f(    1,048,576):         1,348,169:      1.636 [     0.016 :      1.231]
Elapsed count f(    2,097,152):         2,396,745:      1.778 [     0.017 :      1.063]
Elapsed count f(    4,194,304):         6,591,049:      2.750 [     0.095 :      5.588]
Elapsed count f(    8,388,608):        10,785,353:      1.636 [     0.043 :      0.453]
Elapsed count f(   16,777,216):        19,173,961:      1.778 [     0.060 :      1.395]
Elapsed count f(   33,554,432):        52,728,393:      2.750 [     0.733 :     12.217]
Elapsed count f(   67,108,864):        86,282,825:      1.636 [     0.298 :      0.407]
Average delta: 2.055

N pushes in linear time

Each time we resize: constant pushes multiply by 8

Each push is amortized constant time

XPerformanceOfArrays *1.5 [9/13]

01
02
03
04
05
 
  public void push(double item) {
    if (N == a.length) resize((int)Math.ceil (N*1.5));
    a[N] = item;
    N += 1;
  }

Output 

00 
00 01 
00 01 02 
00 01 02 03 04 
00 01 02 03 04 05 06 07 
00 01 02 03 04 05 06 07 08 09 10 11 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
Elapsed count f(          512):             1,922:      2.189 [     0.000 :        NaN]
Elapsed count f(        1,024):             3,144:      1.636 [     0.001 :   Infinity]
Elapsed count f(        2,048):             6,831:      2.173 [     0.000 :      0.000]
Elapsed count f(        4,096):            14,872:      2.177 [     0.000 :        NaN]
Elapsed count f(        8,192):            32,453:      2.182 [     0.001 :   Infinity]
Elapsed count f(       16,384):            52,782:      1.626 [     0.002 :      2.000]
Elapsed count f(       32,768):           114,681:      2.173 [     0.002 :      1.000]
Elapsed count f(       65,536):           249,859:      2.179 [     0.003 :      1.500]
Elapsed count f(      131,072):           407,564:      1.631 [     0.004 :      1.333]
Elapsed count f(      262,144):           884,271:      2.170 [     0.006 :      1.500]
Elapsed count f(      524,288):         1,924,095:      2.176 [     0.012 :      2.000]
Elapsed count f(    1,048,576):         3,148,295:      1.636 [     0.020 :      1.667]
Elapsed count f(    2,097,152):         6,821,541:      2.167 [     0.039 :      1.950]
Elapsed count f(    4,194,304):        14,824,201:      2.173 [     0.042 :      1.077]
Elapsed count f(    8,388,608):        32,305,900:      2.179 [     0.147 :      3.500]
Elapsed count f(   16,777,216):        52,653,164:      1.630 [     0.150 :      1.020]
Elapsed count f(   33,554,432):       114,275,340:      2.170 [     0.508 :      3.387]
Elapsed count f(   67,108,864):       248,730,932:      2.177 [     1.268 :      2.496]
Average delta: 2.025

N pushes in linear time

Each time we resize: constant pushes multiply by 1.5

Each push is amortized constant time

XPerformanceOfArrays *1.1 [10/13]

01
02
03
04
05
 
  public void push(double item) {
    if (N == a.length) resize((int)Math.ceil (N*1.1));
    a[N] = item;
    N += 1;
  }

Output 

00 
00 01 
00 01 02 
00 01 02 03 
00 01 02 03 04 
00 01 02 03 04 05 
00 01 02 03 04 05 06 
00 01 02 03 04 05 06 07 
00 01 02 03 04 05 06 07 08 
00 01 02 03 04 05 06 07 08 09 
00 01 02 03 04 05 06 07 08 09 10 
00 01 02 03 04 05 06 07 08 09 10 11 12 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
Elapsed count f(          512):             5,721:      2.024 [     0.001 :   Infinity]
Elapsed count f(        1,024):            11,402:      1.993 [     0.001 :      1.000]
Elapsed count f(        2,048):            22,520:      1.975 [     0.002 :      2.000]
Elapsed count f(        4,096):            48,320:      2.146 [     0.001 :      0.500]
Elapsed count f(        8,192):            94,698:      1.960 [     0.002 :      2.000]
Elapsed count f(       16,384):           185,318:      1.957 [     0.005 :      2.500]
Elapsed count f(       32,768):           362,372:      1.955 [     0.006 :      1.200]
Elapsed count f(       65,536):           772,598:      2.132 [     0.012 :      2.000]
Elapsed count f(      131,072):         1,509,413:      1.954 [     0.018 :      1.500]
Elapsed count f(      262,144):         2,948,653:      1.954 [     0.018 :      1.000]
Elapsed count f(      524,288):         6,283,714:      2.131 [     0.048 :      2.667]
Elapsed count f(    1,048,576):        12,272,649:      1.953 [     0.046 :      0.958]
Elapsed count f(    2,097,152):        23,970,316:      1.953 [     0.051 :      1.109]
Elapsed count f(    4,194,304):        46,819,577:      1.953 [     0.102 :      2.000]
Elapsed count f(    8,388,608):        99,760,500:      2.131 [     0.223 :      2.186]
Elapsed count f(   16,777,216):       194,835,921:      1.953 [     0.454 :      2.036]
Elapsed count f(   33,554,432):       380,541,255:      1.953 [     0.953 :      2.099]
Elapsed count f(   67,108,864):       743,288,834:      1.953 [     1.579 :      1.657]
Average delta: 2.002

N pushes in linear time

Each time we resize: constant pushes multiply by 1.1

Each push is amortized constant time

The choice of multiplier value is a tradeoff between time and space.

XPerformanceOfStrings [11/13]

Strings are typically implemented as arrays of characters.

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

file:XPerformanceOfStrings.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
package algs14;
import stdlib.*;
public class XPerformanceOfStrings {
  /** create a string consisting of N asterisks */
  public static String makeStringUsingConcat (int N) {
    String result = "";
    for (int i=0; i<N; i+=1) {
      result = result + "*";
      ops += result.length();
    }
    return result;
  }
  /** create a string consisting of N asterisks */
  public static String makeStringUsingBuffer (int N) {
    StringBuffer result = new StringBuffer ();
    for (int i=0; i<N; i+=1) { 
      result.append ("*");
      ops += 1;
    }
    return result.toString ();
  }
  private static long ops;
  private static String result;
  public static void main(String[] args) {
    timeTrial(32);
    StdOut.println(result);
    
    int MIN = 256; 
    int MAX = 1_000_000_000;
    double prevTime = timeTrial(MIN);
    double prevOps = ops;
    for (int N = MIN*2; N<=MAX; N += N) {
      double time = timeTrial(N);
      StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, ops, ops / prevOps, time, time/prevTime);
      prevTime = time;
      prevOps = ops;
    }
  }
  public static double timeTrial(int N) {
    ops = 0;
    Stopwatch sw = new Stopwatch();
    result = makeStringUsingConcat(N);
    //result = makeStringUsingBuffer(N);    
    return sw.elapsedTime();
  }
}

XPerformanceOfStrings [12/13]

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

01
02
03
04
05
06
07
 
  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):

01
02
03
04
05
06
07
 
  public static String toString () {
    String result = "";
    for (int i=0; i<N; i+=1) {
      result = result + a[i];
    }
    return result;
  }

XPerformanceOfStrings [13/13]

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

01
02
03
04
05
06
07
 
  public static String makeStringUsingBuffer (int N) {
    StringBuffer result = new StringBuffer ();
    for (int i=0; i<N; i+=1) { 
      result.append ("*");
    }
    return result.toString ();
  }

Output 

********************************
Elapsed count f(          512):               512:      2.000 [     0.001 :   Infinity]
Elapsed count f(        1,024):             1,024:      2.000 [     0.000 :      0.000]
Elapsed count f(        2,048):             2,048:      2.000 [     0.000 :        NaN]
Elapsed count f(        4,096):             4,096:      2.000 [     0.000 :        NaN]
Elapsed count f(        8,192):             8,192:      2.000 [     0.001 :   Infinity]
Elapsed count f(       16,384):            16,384:      2.000 [     0.002 :      2.000]
Elapsed count f(       32,768):            32,768:      2.000 [     0.002 :      1.000]
Elapsed count f(       65,536):            65,536:      2.000 [     0.002 :      1.000]
Elapsed count f(      131,072):           131,072:      2.000 [     0.004 :      2.000]
Elapsed count f(      262,144):           262,144:      2.000 [     0.007 :      1.750]
Elapsed count f(      524,288):           524,288:      2.000 [     0.008 :      1.143]
Elapsed count f(    1,048,576):         1,048,576:      2.000 [     0.014 :      1.750]
Elapsed count f(    2,097,152):         2,097,152:      2.000 [     0.037 :      2.643]
Elapsed count f(    4,194,304):         4,194,304:      2.000 [     0.057 :      1.541]
Elapsed count f(    8,388,608):         8,388,608:      2.000 [     0.120 :      2.105]
Elapsed count f(   16,777,216):        16,777,216:      2.000 [     0.229 :      1.908]
Elapsed count f(   33,554,432):        33,554,432:      2.000 [     0.430 :      1.878]
Elapsed count f(   67,108,864):        67,108,864:      2.000 [     0.879 :      2.044]
Elapsed count f(  134,217,728):       134,217,728:      2.000 [     1.843 :      2.097]
Elapsed count f(  268,435,456):       268,435,456:      2.000 [     3.706 :      2.011]
Elapsed count f(  536,870,912):       536,870,912:      2.000 [     7.635 :      2.060]

N appends in linear time

Each append is amortized constant time

Java's StringBuffer is implemented with a resizing array.

Note: To see StringBuilder in action, see ResizingArrayQueue and ResizingArrayStack in package algs13.
They each have an implementation of Java's toString method that makes use of StringBuilder.