CSC300 / CSC402: 2D N * lg(N) [5/18] Previous pageContentsNext page

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

Previous pageContentsNext page