CSC300 / CSC402: XPerformanceOfArrays *8 [8/13]

  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