CSC300 / CSC402: XPerformanceOfArrays +1 [3/13] Previous pageContentsNext page

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

Previous pageContentsNext page