CSC300 / CSC402: XPerformanceOfArrays +100 [5/13]

  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