CSC300 / CSC402: 2D N * lg(N) - Flat Pack [6/18] Previous pageContentsNext page

01
02
03
04
05
    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)

Previous pageContentsNext page