| CSC300: 2D N * lg(N) - Flat Pack [7/19] | |
01 |
for (long i = 1; i <= N; i = i*2) { for (long j = i + 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 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 08 08 08 08 08 08 08 08 Elapsed count f( 512): 4,097: 2.285 [ 0.001 : Infinity] Elapsed count f( 1,024): 9,217: 2.250 [ 0.001 : 1.000] Elapsed count f( 2,048): 20,481: 2.222 [ 0.001 : 1.000] Elapsed count f( 4,096): 45,057: 2.200 [ 0.001 : 1.000] Elapsed count f( 8,192): 98,305: 2.182 [ 0.000 : 0.000] Elapsed count f( 16,384): 212,993: 2.167 [ 0.001 : Infinity] Elapsed count f( 32,768): 458,753: 2.154 [ 0.001 : 1.000] Elapsed count f( 65,536): 983,041: 2.143 [ 0.000 : 0.000] Elapsed count f( 131,072): 2,097,153: 2.133 [ 0.002 : Infinity] Elapsed count f( 262,144): 4,456,449: 2.125 [ 0.003 : 1.500] Elapsed count f( 524,288): 9,437,185: 2.118 [ 0.006 : 2.000] Elapsed count f( 1,048,576): 19,922,945: 2.111 [ 0.013 : 2.167] Elapsed count f( 2,097,152): 41,943,041: 2.105 [ 0.026 : 2.000] Elapsed count f( 4,194,304): 88,080,385: 2.100 [ 0.057 : 2.192] Elapsed count f( 8,388,608): 184,549,377: 2.095 [ 0.145 : 2.544] Elapsed count f( 16,777,216): 385,875,969: 2.091 [ 0.260 : 1.793] Elapsed count f( 33,554,432): 805,306,369: 2.087 [ 0.517 : 1.988] Elapsed count f( 67,108,864): 1,677,721,601: 2.083 [ 1.020 : 1.973] Elapsed count f( 134,217,728): 3,489,660,929: 2.080 [ 2.126 : 2.084] Elapsed count f( 268,435,456): 7,247,757,313: 2.077 [ 4.608 : 2.167] Elapsed count f( 536,870,912): 15,032,385,537: 2.074 [ 9.334 : 2.026] Elapsed count f(1,073,741,824): 31,138,512,897: 2.071 [ 19.133 : 2.050] Elapsed count f(2,147,483,648): 64,424,509,441: 2.069 [ 40.003 : 2.091]
This is linearithmic: ~ N * lg(N)
More accurately: (N * lg(N)) - (2N - 1)