# CSC300: Experiments with Time Complexity

 Contents [0/19]

 Video [1/19] XCountingLoops [2/19] 2D Square [3/19] 2D Triangle [4/19] 2D Flat Pack [5/19] 2D N * lg(N) [6/19] 2D N * lg(N) - Flat Pack [7/19] 2D lg(N) * lg(N) [8/19] 3D Cube [9/19] 3D Pyramid [10/19] 4D Cube [11/19] 4D Pyramid [12/19] 5D Cube [13/19] 5D Pyramid [14/19] XCountingRecursion [15/19] Recursive Factorial [16/19] Recursive Fibonacci (Terrible Version) [17/19] String Concatenation (Recursive) [18/19] String Concatenation (Loop) [19/19]

 Video [1/19]

In three parts

 Open Playlist
 Open Playlist
 Open Playlist

 XCountingLoops [2/19]

 file:XCountingLoops.java [source] [doc-public] [doc-private]
 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 package algs14; import stdlib.*; public class XCountingLoops { // To Print: StdOut.printf ("N=%3d i=%3d N-i=%d\n", N, i, N-i); // // Test variant with one, two or three nested loops // // Outermost: // for (long i = 1; i <= N; i = i+1) { // for (long i = 1; i <= N; i = i*2) { // // Next: // for (long j = 1; j <= N; j = j+1) { // for (long j = 1; j <= i; j = j+1) { // for (long j = 1; j <= N; j = j*2) { // for (long j = 1; j <= i; j = j*2) { // // Next: // for (long k = 1; k <= N; k = k+1) { // for (long k = 1; k <= j; k = k+1) { // for (long k = 1; k <= N; k = k*2) { // for (long k = 1; k <= j; k = k*2) { // f counts the number of times the innermost loop executes static long f (long N) { long result = 0; for (long i = 1; i <= N; i = i+1) { for (long j = 1; j <= N; j = j+1) { result = result+1; if (N <= 64) StdOut.format ("%02d ", i); } if (N <= 64) StdOut.println (); } return result; } public static void main (String[] args) { f(16); long MIN = 256L; // for powers of ten, start with 500L long MAX = 3_200_000_000L; Stopwatch sw = new Stopwatch (); double prevCount = f(MIN); double prevTime = sw.elapsedTime (); for (long N = MIN*2; N <= MAX; N=N*2) { sw = new Stopwatch (); long count = f(N); double time = sw.elapsedTime (); StdOut.format ("Elapsed count f(%,13d): %,16d: %10.3f [%10.3f : %10.3f]\n", N, count, count / prevCount, time, time/prevTime); //StdOut.format ("Elapsed count f(%,13d): %,16d: %10.3f\n", N, count, count / prevCount); prevCount = count; prevTime = time; } } }

 2D Square [3/19]

 01 02 03 04 05 for (long i = 1; i <= N; i = i+1) { 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
03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
04 04 04 04 04 04 04 04 04 04 04 04 04 04 04 04
05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05
06 06 06 06 06 06 06 06 06 06 06 06 06 06 06 06
07 07 07 07 07 07 07 07 07 07 07 07 07 07 07 07
08 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08
09 09 09 09 09 09 09 09 09 09 09 09 09 09 09 09
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12
13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13
14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16
Elapsed count f(          512):          262,144:      4.000 [     0.003 :      0.750]
Elapsed count f(        1,024):        1,048,576:      4.000 [     0.001 :      0.333]
Elapsed count f(        2,048):        4,194,304:      4.000 [     0.006 :      6.000]
Elapsed count f(        4,096):       16,777,216:      4.000 [     0.032 :      5.333]
Elapsed count f(        8,192):       67,108,864:      4.000 [     0.056 :      1.750]
Elapsed count f(       16,384):      268,435,456:      4.000 [     0.152 :      2.714]
Elapsed count f(       32,768):    1,073,741,824:      4.000 [     0.546 :      3.592]
Elapsed count f(       65,536):    4,294,967,296:      4.000 [     2.228 :      4.081]
Elapsed count f(      131,072):   17,179,869,184:      4.000 [     9.405 :      4.221]
Elapsed count f(      262,144):   68,719,476,736:      4.000 [    35.069 :      3.729]
Elapsed count f(      524,288) aborted execution after a minute or so
Elapsed count f(    1,048,576) aborted execution after a minute or so
Elapsed count f(    2,097,152) aborted execution after a minute or so
Elapsed count f(    4,194,304) aborted execution after a minute or so
Elapsed count f(    8,388,608) aborted execution after a minute or so
Elapsed count f(   16,777,216) aborted execution after a minute or so
Elapsed count f(   33,554,432) aborted execution after a minute or so
Elapsed count f(   67,108,864) aborted execution after a minute or so
Elapsed count f(  134,217,728) aborted execution after a minute or so
Elapsed count f(  268,435,456) aborted execution after a minute or so
Elapsed count f(  536,870,912) aborted execution after a minute or so
Elapsed count f(1,073,741,824) aborted execution after a minute or so
Elapsed count f(2,147,483,648) aborted execution after a minute or so

 2D Triangle [4/19]

 01 02 03 04 05 for (long i = 1; i <= N; i = i+1) { for (long j = 1; j <= i; j = j+1) { result = result+1; } }

Output

01
02 02
03 03 03
04 04 04 04
05 05 05 05 05
06 06 06 06 06 06
07 07 07 07 07 07 07
08 08 08 08 08 08 08 08
09 09 09 09 09 09 09 09 09
10 10 10 10 10 10 10 10 10 10
11 11 11 11 11 11 11 11 11 11 11
12 12 12 12 12 12 12 12 12 12 12 12
13 13 13 13 13 13 13 13 13 13 13 13 13
14 14 14 14 14 14 14 14 14 14 14 14 14 14
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16
Elapsed count f(          512):          131,328:      3.992 [     0.002 :      2.000]
Elapsed count f(        1,024):          524,800:      3.996 [     0.003 :      1.500]
Elapsed count f(        2,048):        2,098,176:      3.998 [     0.002 :      0.667]
Elapsed count f(        4,096):        8,390,656:      3.999 [     0.005 :      2.500]
Elapsed count f(        8,192):       33,558,528:      4.000 [     0.016 :      3.200]
Elapsed count f(       16,384):      134,225,920:      4.000 [     0.065 :      4.063]
Elapsed count f(       32,768):      536,887,296:      4.000 [     0.246 :      3.785]
Elapsed count f(       65,536):    2,147,516,416:      4.000 [     1.001 :      4.069]
Elapsed count f(      131,072):    8,590,000,128:      4.000 [     4.006 :      4.002]
Elapsed count f(      262,144):   34,359,869,440:      4.000 [    15.628 :      3.901]
Elapsed count f(      524,288):  137,439,215,616:      4.000 [    62.422 :      3.994]
Elapsed count f(    1,048,576) aborted execution after a minute or so
Elapsed count f(    2,097,152) aborted execution after a minute or so
Elapsed count f(    4,194,304) aborted execution after a minute or so
Elapsed count f(    8,388,608) aborted execution after a minute or so
Elapsed count f(   16,777,216) aborted execution after a minute or so
Elapsed count f(   33,554,432) aborted execution after a minute or so
Elapsed count f(   67,108,864) aborted execution after a minute or so
Elapsed count f(  134,217,728) aborted execution after a minute or so
Elapsed count f(  268,435,456) aborted execution after a minute or so
Elapsed count f(  536,870,912) aborted execution after a minute or so
Elapsed count f(1,073,741,824) aborted execution after a minute or so
Elapsed count f(2,147,483,648) aborted execution after a minute or so

This is quadratic: ~ 1/2 * N^2

More accurately: (1/2 * N^2) - N/2

 2D Flat Pack [5/19]

 01 02 03 04 05 for (long i = 1; i <= N; i = i*2) { for (long j = 1; j <= i; j = j+1) { result = result+1; } }

Output

01
02 02
04 04 04 04
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):            1,023:      2.002 [     0.000 :        NaN]
Elapsed count f(        1,024):            2,047:      2.001 [     0.000 :        NaN]
Elapsed count f(        2,048):            4,095:      2.000 [     0.001 :   Infinity]
Elapsed count f(        4,096):            8,191:      2.000 [     0.000 :      0.000]
Elapsed count f(        8,192):           16,383:      2.000 [     0.001 :   Infinity]
Elapsed count f(       16,384):           32,767:      2.000 [     0.003 :      3.000]
Elapsed count f(       32,768):           65,535:      2.000 [     0.001 :      0.333]
Elapsed count f(       65,536):          131,071:      2.000 [     0.003 :      3.000]
Elapsed count f(      131,072):          262,143:      2.000 [     0.000 :      0.000]
Elapsed count f(      262,144):          524,287:      2.000 [     0.001 :   Infinity]
Elapsed count f(      524,288):        1,048,575:      2.000 [     0.001 :      1.000]
Elapsed count f(    1,048,576):        2,097,151:      2.000 [     0.002 :      2.000]
Elapsed count f(    2,097,152):        4,194,303:      2.000 [     0.003 :      1.500]
Elapsed count f(    4,194,304):        8,388,607:      2.000 [     0.010 :      3.333]
Elapsed count f(    8,388,608):       16,777,215:      2.000 [     0.019 :      1.900]
Elapsed count f(   16,777,216):       33,554,431:      2.000 [     0.033 :      1.737]
Elapsed count f(   33,554,432):       67,108,863:      2.000 [     0.041 :      1.242]
Elapsed count f(   67,108,864):      134,217,727:      2.000 [     0.092 :      2.244]
Elapsed count f(  134,217,728):      268,435,455:      2.000 [     0.169 :      1.837]
Elapsed count f(  268,435,456):      536,870,911:      2.000 [     0.292 :      1.728]
Elapsed count f(  536,870,912):    1,073,741,823:      2.000 [     0.553 :      1.894]
Elapsed count f(1,073,741,824):    2,147,483,647:      2.000 [     1.149 :      2.078]
Elapsed count f(2,147,483,648):    4,294,967,295:      2.000 [     2.284 :      1.988]

This is linear: ~ 2N

More accurately: 2N - 1

 2D N * lg(N) [6/19]

 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)

 2D N * lg(N) - Flat Pack [7/19]

 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)

 2D lg(N) * lg(N) [8/19]

 01 02 03 04 05 for (long i = 1; i <= N; i = i*2) { for (long j = 1; j <= N; j = j*2) { result = result+1; } }

Output

01 01 01 01 01
02 02 02 02 02
04 04 04 04 04
08 08 08 08 08
16 16 16 16 16

Elapsed count f(          512):              100:      1.235 [     0.000 :        NaN]
Elapsed count f(        1,024):              121:      1.210 [     0.000 :        NaN]
Elapsed count f(        2,048):              144:      1.190 [     0.000 :        NaN]
Elapsed count f(        4,096):              169:      1.174 [     0.000 :        NaN]
Elapsed count f(        8,192):              196:      1.160 [     0.000 :        NaN]
Elapsed count f(       16,384):              225:      1.148 [     0.000 :        NaN]
Elapsed count f(       32,768):              256:      1.138 [     0.000 :        NaN]
Elapsed count f(       65,536):              289:      1.129 [     0.000 :        NaN]
Elapsed count f(      131,072):              324:      1.121 [     0.000 :        NaN]
Elapsed count f(      262,144):              361:      1.114 [     0.000 :        NaN]
Elapsed count f(      524,288):              400:      1.108 [     0.000 :        NaN]
Elapsed count f(    1,048,576):              441:      1.103 [     0.000 :        NaN]
Elapsed count f(    2,097,152):              484:      1.098 [     0.000 :        NaN]
Elapsed count f(    4,194,304):              529:      1.093 [     0.000 :        NaN]
Elapsed count f(    8,388,608):              576:      1.089 [     0.000 :        NaN]
Elapsed count f(   16,777,216):              625:      1.085 [     0.000 :        NaN]
Elapsed count f(   33,554,432):              676:      1.082 [     0.000 :        NaN]
Elapsed count f(   67,108,864):              729:      1.078 [     0.000 :        NaN]
Elapsed count f(  134,217,728):              784:      1.075 [     0.000 :        NaN]
Elapsed count f(  268,435,456):              841:      1.073 [     0.000 :        NaN]
Elapsed count f(  536,870,912):              900:      1.070 [     0.001 :   Infinity]
Elapsed count f(1,073,741,824):              961:      1.068 [     0.000 :      0.000]
Elapsed count f(2,147,483,648):            1,024:      1.066 [     0.000 :        NaN]

This is log squared: ~ lg(N) * lg(N)

 3D Cube [9/19]

 01 02 03 04 05 06 07 for (long i = 1; i <= N; i = i+1) { for (long j = 1; j <= N; j = j+1) { for (long k = 1; k <= N; k = k+1) { result = result+1; } } }

Output

Elapsed count f(            8):              512:      8.000 [     0.000 :        NaN]
Elapsed count f(           16):            4,096:      8.000 [     0.000 :        NaN]
Elapsed count f(           32):           32,768:      8.000 [     0.000 :        NaN]
Elapsed count f(           64):          262,144:      8.000 [     0.001 :   Infinity]
Elapsed count f(          128):        2,097,152:      8.000 [     0.004 :      4.000]
Elapsed count f(          256):       16,777,216:      8.000 [     0.008 :      2.000]
Elapsed count f(          512):      134,217,728:      8.000 [     0.063 :      7.875]
Elapsed count f(        1,024):    1,073,741,824:      8.000 [     0.532 :      8.444]
Elapsed count f(        2,048):    8,589,934,592:      8.000 [     3.979 :      7.479]
Elapsed count f(        4,096):   68,719,476,736:      8.000 [    31.300 :      7.866]
Elapsed count f(        8,192):  549,755,813,888:      8.000 [   253.206 :      8.090]
Elapsed count f(       16,384) aborted execution after a minute or so
Elapsed count f(       32,768) aborted execution after a minute or so
Elapsed count f(       65,536) aborted execution after a minute or so
Elapsed count f(      131,072) aborted execution after a minute or so
Elapsed count f(      262,144) aborted execution after a minute or so
Elapsed count f(      524,288) aborted execution after a minute or so
Elapsed count f(    1,048,576) aborted execution after a minute or so
Elapsed count f(    2,097,152) aborted execution after a minute or so
Elapsed count f(    4,194,304) aborted execution after a minute or so
Elapsed count f(    8,388,608) aborted execution after a minute or so
Elapsed count f(   16,777,216) aborted execution after a minute or so
Elapsed count f(   33,554,432) aborted execution after a minute or so
Elapsed count f(   67,108,864) aborted execution after a minute or so
Elapsed count f(  134,217,728) aborted execution after a minute or so
Elapsed count f(  268,435,456) aborted execution after a minute or so
Elapsed count f(  536,870,912) aborted execution after a minute or so
Elapsed count f(1,073,741,824) aborted execution after a minute or so
Elapsed count f(2,147,483,648) aborted execution after a minute or so

This is cubic: ~ N^3

 3D Pyramid [10/19]

 01 02 03 04 05 06 07 for (long i = 1; i <= N; i = i+1) { for (long j = 1; j <= i; j = j+1) { for (long k = 1; k <= j; k = k+1) { result = result+1; } } }

Output

Elapsed count f(            8):              120:      6.000 [     0.000 :        NaN]
Elapsed count f(           16):              816:      6.800 [     0.000 :        NaN]
Elapsed count f(           32):            5,984:      7.333 [     0.000 :        NaN]
Elapsed count f(           64):           45,760:      7.647 [     0.001 :   Infinity]
Elapsed count f(          128):          357,760:      7.818 [     0.001 :      1.000]
Elapsed count f(          256):        2,829,056:      7.908 [     0.005 :      5.000]
Elapsed count f(          512):       22,500,864:      7.953 [     0.011 :      2.200]
Elapsed count f(        1,024):      179,481,600:      7.977 [     0.091 :      8.273]
Elapsed count f(        2,048):    1,433,753,600:      7.988 [     0.683 :      7.505]
Elapsed count f(        4,096):   11,461,636,096:      7.994 [     5.322 :      7.792]
Elapsed count f(        8,192):   91,659,526,144:      7.997 [    42.736 :      8.030]
Elapsed count f(       16,384) aborted execution after a minute or so
Elapsed count f(       32,768) aborted execution after a minute or so
Elapsed count f(       65,536) aborted execution after a minute or so
Elapsed count f(      131,072) aborted execution after a minute or so
Elapsed count f(      262,144) aborted execution after a minute or so
Elapsed count f(      524,288) aborted execution after a minute or so
Elapsed count f(    1,048,576) aborted execution after a minute or so
Elapsed count f(    2,097,152) aborted execution after a minute or so
Elapsed count f(    4,194,304) aborted execution after a minute or so
Elapsed count f(    8,388,608) aborted execution after a minute or so
Elapsed count f(   16,777,216) aborted execution after a minute or so
Elapsed count f(   33,554,432) aborted execution after a minute or so
Elapsed count f(   67,108,864) aborted execution after a minute or so
Elapsed count f(  134,217,728) aborted execution after a minute or so
Elapsed count f(  268,435,456) aborted execution after a minute or so
Elapsed count f(  536,870,912) aborted execution after a minute or so
Elapsed count f(1,073,741,824) aborted execution after a minute or so
Elapsed count f(2,147,483,648) aborted execution after a minute or so

This is cubic: ~ 1/6 * N^3

It's a tetrahedron (image from Dune Project):

 4D Cube [11/19]

 01 02 03 04 05 06 07 08 09 for (long i = 1; i <= N; i = i+1) { for (long j = 1; j <= N; j = j+1) { for (long k = 1; k <= N; k = k+1) { for (long l = 1; l <= N; l = l+1) { result = result+1; } } } }

Output

Elapsed count f(            8):            4,096:     16.000 [     0.000 :        NaN]
Elapsed count f(           16):           65,536:     16.000 [     0.000 :        NaN]
Elapsed count f(           32):        1,048,576:     16.000 [     0.003 :   Infinity]
Elapsed count f(           64):       16,777,216:     16.000 [     0.026 :      8.667]
Elapsed count f(          128):      268,435,456:     16.000 [     0.140 :      5.385]
Elapsed count f(          256):    4,294,967,296:     16.000 [     2.014 :     14.386]
Elapsed count f(          512):   68,719,476,736:     16.000 [    31.673 :     15.726]
Elapsed count f(        1,024) aborted execution after a minute or so
Elapsed count f(        2,048) aborted execution after a minute or so
Elapsed count f(        4,096) aborted execution after a minute or so
Elapsed count f(        8,192) aborted execution after a minute or so
Elapsed count f(       16,384) aborted execution after a minute or so
Elapsed count f(       32,768) aborted execution after a minute or so
Elapsed count f(       65,536) aborted execution after a minute or so
Elapsed count f(      131,072) aborted execution after a minute or so
Elapsed count f(      262,144) aborted execution after a minute or so
Elapsed count f(      524,288) aborted execution after a minute or so
Elapsed count f(    1,048,576) aborted execution after a minute or so
Elapsed count f(    2,097,152) aborted execution after a minute or so
Elapsed count f(    4,194,304) aborted execution after a minute or so
Elapsed count f(    8,388,608) aborted execution after a minute or so
Elapsed count f(   16,777,216) aborted execution after a minute or so
Elapsed count f(   33,554,432) aborted execution after a minute or so
Elapsed count f(   67,108,864) aborted execution after a minute or so
Elapsed count f(  134,217,728) aborted execution after a minute or so
Elapsed count f(  268,435,456) aborted execution after a minute or so
Elapsed count f(  536,870,912) aborted execution after a minute or so
Elapsed count f(1,073,741,824) aborted execution after a minute or so
Elapsed count f(2,147,483,648) aborted execution after a minute or so

This is quartic: ~ N^4

 4D Pyramid [12/19]

 01 02 03 04 05 06 07 08 09 for (long i = 1; i <= N; i = i+1) { for (long j = 1; j <= i; j = j+1) { for (long k = 1; k <= j; k = k+1) { for (long l = 1; l <= k; l = l+1) { result = result+1; } } } }

Output

Elapsed count f(            8):              330:      9.429 [     0.000 :        NaN]
Elapsed count f(           16):            3,876:     11.745 [     0.001 :   Infinity]
Elapsed count f(           32):           52,360:     13.509 [     0.001 :      1.000]
Elapsed count f(           64):          766,480:     14.639 [     0.002 :      2.000]
Elapsed count f(          128):       11,716,640:     15.286 [     0.008 :      4.000]
Elapsed count f(          256):      183,181,376:     15.634 [     0.277 :     34.625]
Elapsed count f(          512):    2,896,986,240:     15.815 [     4.417 :     15.946]
Elapsed count f(        1,024):   46,081,900,800:     15.907 [    68.227 :     15.446]
Elapsed count f(        2,048) aborted execution after a minute or so
Elapsed count f(        4,096) aborted execution after a minute or so
Elapsed count f(        8,192) aborted execution after a minute or so
Elapsed count f(       16,384) aborted execution after a minute or so
Elapsed count f(       32,768) aborted execution after a minute or so
Elapsed count f(       65,536) aborted execution after a minute or so
Elapsed count f(      131,072) aborted execution after a minute or so
Elapsed count f(      262,144) aborted execution after a minute or so
Elapsed count f(      524,288) aborted execution after a minute or so
Elapsed count f(    1,048,576) aborted execution after a minute or so
Elapsed count f(    2,097,152) aborted execution after a minute or so
Elapsed count f(    4,194,304) aborted execution after a minute or so
Elapsed count f(    8,388,608) aborted execution after a minute or so
Elapsed count f(   16,777,216) aborted execution after a minute or so
Elapsed count f(   33,554,432) aborted execution after a minute or so
Elapsed count f(   67,108,864) aborted execution after a minute or so
Elapsed count f(  134,217,728) aborted execution after a minute or so
Elapsed count f(  268,435,456) aborted execution after a minute or so
Elapsed count f(  536,870,912) aborted execution after a minute or so
Elapsed count f(1,073,741,824) aborted execution after a minute or so
Elapsed count f(2,147,483,648) aborted execution after a minute or so

This is quartic: ~ 1/24 * N^4

 5D Cube [13/19]

 01 02 03 04 05 06 07 08 09 10 11 for (long i = 1; i <= N; i = i+1) { for (long j = 1; j <= N; j = j+1) { for (long k = 1; k <= N; k = k+1) { for (long l = 1; l <= N; l = l+1) { for (long m = 1; m <= N; m = m+1) { result = result+1; } } } } }

Output

Elapsed count f(            8):           32,768:     32.000 [     0.000 :        NaN]
Elapsed count f(           16):        1,048,576:     32.000 [     0.000 :        NaN]
Elapsed count f(           32):       33,554,432:     32.000 [     0.014 :   Infinity]
Elapsed count f(           64):    1,073,741,824:     32.000 [     0.620 :     44.286]
Elapsed count f(          128):   34,359,738,368:     32.000 [    17.720 :     28.581]
Elapsed count f(          256) aborted execution after a minute or so
Elapsed count f(          512) aborted execution after a minute or so
Elapsed count f(        1,024) aborted execution after a minute or so
Elapsed count f(        2,048) aborted execution after a minute or so
Elapsed count f(        4,096) aborted execution after a minute or so
Elapsed count f(        8,192) aborted execution after a minute or so
Elapsed count f(       16,384) aborted execution after a minute or so
Elapsed count f(       32,768) aborted execution after a minute or so
Elapsed count f(       65,536) aborted execution after a minute or so
Elapsed count f(      131,072) aborted execution after a minute or so
Elapsed count f(      262,144) aborted execution after a minute or so
Elapsed count f(      524,288) aborted execution after a minute or so
Elapsed count f(    1,048,576) aborted execution after a minute or so
Elapsed count f(    2,097,152) aborted execution after a minute or so
Elapsed count f(    4,194,304) aborted execution after a minute or so
Elapsed count f(    8,388,608) aborted execution after a minute or so
Elapsed count f(   16,777,216) aborted execution after a minute or so
Elapsed count f(   33,554,432) aborted execution after a minute or so
Elapsed count f(   67,108,864) aborted execution after a minute or so
Elapsed count f(  134,217,728) aborted execution after a minute or so
Elapsed count f(  268,435,456) aborted execution after a minute or so
Elapsed count f(  536,870,912) aborted execution after a minute or so
Elapsed count f(1,073,741,824) aborted execution after a minute or so
Elapsed count f(2,147,483,648) aborted execution after a minute or so

This is quintic: ~ N^5

 5D Pyramid [14/19]

 01 02 03 04 05 06 07 08 09 10 11 for (long i = 1; i <= N; i = i+1) { for (long j = 1; j <= i; j = j+1) { for (long k = 1; k <= j; k = k+1) { for (long l = 1; l <= k; l = l+1) { for (long m = 1; m <= l; m = m+1) { result = result+1; } } } } }

Output

Elapsed count f(            8):              792:     14.143 [     0.000 :        NaN]
Elapsed count f(           16):           15,504:     19.576 [     0.001 :   Infinity]
Elapsed count f(           32):          376,992:     24.316 [     0.003 :      3.000]
Elapsed count f(           64):       10,424,128:     27.651 [     0.018 :      6.000]
Elapsed count f(          128):      309,319,296:     29.673 [     0.491 :     27.278]
Elapsed count f(          256):    9,525,431,552:     30.795 [     5.574 :     11.352]
Elapsed count f(          512) aborted execution after a minute or so
Elapsed count f(        1,024) aborted execution after a minute or so
Elapsed count f(        2,048) aborted execution after a minute or so
Elapsed count f(        4,096) aborted execution after a minute or so
Elapsed count f(        8,192) aborted execution after a minute or so
Elapsed count f(       16,384) aborted execution after a minute or so
Elapsed count f(       32,768) aborted execution after a minute or so
Elapsed count f(       65,536) aborted execution after a minute or so
Elapsed count f(      131,072) aborted execution after a minute or so
Elapsed count f(      262,144) aborted execution after a minute or so
Elapsed count f(      524,288) aborted execution after a minute or so
Elapsed count f(    1,048,576) aborted execution after a minute or so
Elapsed count f(    2,097,152) aborted execution after a minute or so
Elapsed count f(    4,194,304) aborted execution after a minute or so
Elapsed count f(    8,388,608) aborted execution after a minute or so
Elapsed count f(   16,777,216) aborted execution after a minute or so
Elapsed count f(   33,554,432) aborted execution after a minute or so
Elapsed count f(   67,108,864) aborted execution after a minute or so
Elapsed count f(  134,217,728) aborted execution after a minute or so
Elapsed count f(  268,435,456) aborted execution after a minute or so
Elapsed count f(  536,870,912) aborted execution after a minute or so
Elapsed count f(1,073,741,824) aborted execution after a minute or so
Elapsed count f(2,147,483,648) aborted execution after a minute or so

This is quintic: ~ 1/120 * N^5

 XCountingRecursion [15/19]

 file:XCountingRecursion.java [source] [doc-public] [doc-private]
 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 package algs14; import stdlib.*; public class XCountingRecursion { /* testing an integer function */ public static long f (long N) { if (N <= 1) { return 1; } else { long result = f(N-1) * N; numOps = numOps + 1; return result; } } // public static String f (long N) { // if (N == 0) { // return ""; // } else { // String result = "*" + f(N - 1); // numOps = numOps + result.length(); // return result; // } // } private static long numOps; public static void main (String[] args) { long MIN = 4L; long MAX = 5000L; // If too big, you may get a StackOverflowException Stopwatch sw = new Stopwatch (); numOps = 0; f(MIN); double prevCount = numOps; double prevTime = sw.elapsedTime (); for (long N = MIN*2; N <= MAX; N=N*2) { sw = new Stopwatch (); numOps = 0; f(N); long count = numOps; double time = sw.elapsedTime (); StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, count, count / prevCount, time, time/prevTime); //StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f\n", N, count, count / prevCount); prevCount = count; prevTime = time; } } }

 Recursive Factorial [16/19]

 01 02 03 04 05 06 07 08 09 public static long f (long N) { if (N <= 1) { return 1; } else { long result = f(N-1) * N; numOps = numOps + 1; return result; } }

Output

Elapsed count f(            8):               7:      2.333 [     0.000 :        NaN]
Elapsed count f(           16):              15:      2.143 [     0.000 :        NaN]
Elapsed count f(           32):              31:      2.067 [     0.000 :        NaN]
Elapsed count f(           64):              63:      2.032 [     0.000 :        NaN]
Elapsed count f(          128):             127:      2.016 [     0.000 :        NaN]
Elapsed count f(          256):             255:      2.008 [     0.000 :        NaN]
Elapsed count f(          512):             511:      2.004 [     0.000 :        NaN]
Elapsed count f(        1,024):           1,023:      2.002 [     0.000 :        NaN]
Elapsed count f(        2,048):           2,047:      2.001 [     0.000 :        NaN]
Elapsed count f(        4,096):           4,095:      2.000 [     0.000 :        NaN]
Elapsed count f(        8,192):           8,191:      2.000 [     0.000 :        NaN]

This is linear: ~ N

 Recursive Fibonacci (Terrible Version) [17/19]

 01 02 03 04 05 06 07 08 09 public static long f (long N) { if (N <= 1) { return N; } else { long result = f(N-1) + f(N-2); numOps = numOps + 1; return result; } }

Output

Elapsed count f(            8):               33:      8.250 [     0.000 :        NaN]
Elapsed count f(           16):            1,596:     48.364 [     0.000 :        NaN]
Elapsed count f(           32):        3,524,577:   2208.382 [     0.011 :   Infinity]
Elapsed count f(           64) aborted execution after a thousand hours or so
Elapsed count f(          128) aborted execution after a thousand hours or so
Elapsed count f(          256) aborted execution after a thousand hours or so
Elapsed count f(          512) aborted execution after a thousand hours or so
Elapsed count f(        1,024) aborted execution after a thousand hours or so
Elapsed count f(        2,048) aborted execution after a thousand hours or so
Elapsed count f(        4,096) aborted execution after a thousand hours or so
Elapsed count f(        8,192) aborted execution after a thousand hours or so

This is exponential: approximately 2^N

More accurately: (1.6)^N, where 1.6 = (1+sqrt(5))/2

 String Concatenation (Recursive) [18/19]

 01 02 03 04 05 06 07 08 09 public static String f (long N) { if (N == 0) { return ""; } else { String result = "*" + f(N - 1); numOps = numOps + result.length(); return result; } }

Output

Elapsed count f(            8):               36:      3.600 [     0.000 :        NaN]
Elapsed count f(           16):              136:      3.778 [     0.000 :        NaN]
Elapsed count f(           32):              528:      3.882 [     0.000 :        NaN]
Elapsed count f(           64):            2,080:      3.939 [     0.001 :   Infinity]
Elapsed count f(          128):            8,256:      3.969 [     0.000 :      0.000]
Elapsed count f(          256):           32,896:      3.984 [     0.000 :        NaN]
Elapsed count f(          512):          131,328:      3.992 [     0.000 :        NaN]
Elapsed count f(        1,024):          524,800:      3.996 [     0.001 :   Infinity]
Elapsed count f(        2,048):        2,098,176:      3.998 [     0.003 :      3.000]
Elapsed count f(        4,096):        8,390,656:      3.999 [     0.012 :      4.000]
at java.base/java.lang.StringBuilder.<init>(StringBuilder.java:124)
at algs14.XCountingRecursion.f(XCountingRecursion.java:18)

 String Concatenation (Loop) [19/19]

 01 02 03 04 05 06 07 08 09 public static String f (long N) { String result = ""; while (N != 0) { N = N - 1; result = "*" + result; numOps = numOps + result.length(); } return result; }

Output

Elapsed count f(            8):               36:      3.600 [     0.000 :        NaN]
Elapsed count f(           16):              136:      3.778 [     0.000 :        NaN]
Elapsed count f(           32):              528:      3.882 [     0.000 :        NaN]
Elapsed count f(           64):            2,080:      3.939 [     0.000 :        NaN]
Elapsed count f(          128):            8,256:      3.969 [     0.000 :        NaN]
Elapsed count f(          256):           32,896:      3.984 [     0.000 :        NaN]
Elapsed count f(          512):          131,328:      3.992 [     0.000 :        NaN]
Elapsed count f(        1,024):          524,800:      3.996 [     0.001 :   Infinity]
Elapsed count f(        2,048):        2,098,176:      3.998 [     0.003 :      3.000]
Elapsed count f(        4,096):        8,390,656:      3.999 [     0.010 :      3.333]
Elapsed count f(        8,192):       33,558,528:      4.000 [     0.041 :      4.100]
Elapsed count f(       16,384):      134,225,920:      4.000 [     0.077 :      1.878]
Elapsed count f(       32,768):      536,887,296:      4.000 [     0.181 :      2.351]
Elapsed count f(       65,536):    2,147,516,416:      4.000 [     0.517 :      2.856]
Elapsed count f(      131,072):    8,590,000,128:      4.000 [     0.847 :      1.638]
Elapsed count f(      262,144):   34,359,869,440:      4.000 [     3.567 :      4.211]
Elapsed count f(      524,288):  137,439,215,616:      4.000 [    13.881 :      3.892]
Elapsed count f(    1,048,576):  549,756,338,176:      4.000 [    62.358 :      4.492]