| CSC300 / CSC402: 2D N * lg(N) [5/18] | |
01 |
for (long i = 1; i <= N; i = i*2) { for (long j = 1; j <= N; j = j+1) { result = result+1; } } |
Output
01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 04 04 04 04 04 04 04 04 04 04 04 04 04 04 04 04 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 Elapsed count f( 512): 5,120: 2.222 [ 0.000 : NaN] Elapsed count f( 1,024): 11,264: 2.200 [ 0.001 : Infinity] Elapsed count f( 2,048): 24,576: 2.182 [ 0.001 : 1.000] Elapsed count f( 4,096): 53,248: 2.167 [ 0.001 : 1.000] Elapsed count f( 8,192): 114,688: 2.154 [ 0.000 : 0.000] Elapsed count f( 16,384): 245,760: 2.143 [ 0.002 : Infinity] Elapsed count f( 32,768): 524,288: 2.133 [ 0.001 : 0.500] Elapsed count f( 65,536): 1,114,112: 2.125 [ 0.001 : 1.000] Elapsed count f( 131,072): 2,359,296: 2.118 [ 0.001 : 1.000] Elapsed count f( 262,144): 4,980,736: 2.111 [ 0.003 : 3.000] Elapsed count f( 524,288): 10,485,760: 2.105 [ 0.006 : 2.000] Elapsed count f( 1,048,576): 22,020,096: 2.100 [ 0.014 : 2.333] Elapsed count f( 2,097,152): 46,137,344: 2.095 [ 0.030 : 2.143] Elapsed count f( 4,194,304): 96,468,992: 2.091 [ 0.054 : 1.800] Elapsed count f( 8,388,608): 201,326,592: 2.087 [ 0.108 : 2.000] Elapsed count f( 16,777,216): 419,430,400: 2.083 [ 0.222 : 2.056] Elapsed count f( 33,554,432): 872,415,232: 2.080 [ 0.505 : 2.275] Elapsed count f( 67,108,864): 1,811,939,328: 2.077 [ 0.972 : 1.925] Elapsed count f( 134,217,728): 3,758,096,384: 2.074 [ 2.057 : 2.116] Elapsed count f( 268,435,456): 7,784,628,224: 2.071 [ 4.106 : 1.996] Elapsed count f( 536,870,912): 16,106,127,360: 2.069 [ 8.241 : 2.007] Elapsed count f(1,073,741,824): 33,285,996,544: 2.067 [ 17.254 : 2.094] Elapsed count f(2,147,483,648): 68,719,476,736: 2.065 [ 35.660 : 2.067]
This is linearithmic: ~ N * lg(N)