CSC300 / CSC402: String Concatenation (Loop) [18/18] Previous pageContents

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]

This is quadratic: approximately N^2

Previous pageContents