CSC300: PerformanceOfArrays +10 [4/13]

  public void append(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 appends in quadratic time

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

Each append is amortized linear time