CSC300 / CSC402: XPerformanceOfArrays *4 [7/13]

  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