| 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] |
(Click here for one slide per page)
| Video [1/19] |
In three parts
you'll learn a lot more about the mathematics of time complexity when you take the algorithms class which is CSC 321 at DePaul in this course we're gonna treat this subject more experimentally and more intuitively I want you to develop good intuitions about how doing tasks repetitively sort of adds up let's first look at a doubly nested loop I have a main program which calls function f with argument 16 I'm going to make it a long because we're gonna start dealing with some pretty big numbers the outer loop iterates from 1 up to n increasing by 1 the inner loop also goes from 1 up to n increasing by 1 and in the loop body I'll simply print the value of the outer loop index variable let's see what we get when we run this it's a square for each value of i from 1 to n we printed that value of i in x that is we've executed this inner loop body in x in x or in squared x we can also see what happens if we vary the loop bounds let's suppose instead of having my inner loop go from 1 to n I have it stopped at I what's the shape I get as a result it's a triangle what's a triangle well that's half of a squared so now we're at about half of N squared what happens if I go through I geometrically instead of arithmetic Li let's change the inductive step to do multiplication and see what happens it's the flat-pack sum so I can take all of the numbers that are smaller than 16 and lay them down on top of the 16s and end up with something that's only two layers deep so what I have here is about two times in and what happens if I change my bound of the inner loop back to n what's happening here is that for each value of I I'm performing linear work but I'm only choosing a logarithmic number of values for I if you want to be precise the exact amount of work here is in for each iteration of I how many iterations if I are there well it's actually the logarithm of n plus 1 because there's five iterations here and the logarithm of 16 is 4 so we have log of n plus 1 iterations I find pictures like this very helpful in understanding the amount of work that a loop is performing but it's also useful sometimes just see the raw numbers what we can do is instrument our code to return the amount of work that it's performed and I'll do this just by introducing a result variable that computes how many times the body of the loop is executed so what I've got here is a result value which is initially 0 each time line 28 execute will increment that by 1 and then return the result what I can do in my main program is write a loop to sort of go over those results and print them out let's see what happens here what's being printed for each test is three numbers first is in that's the size of the tests that's the value I'm currently using for in when I call F the second thing is the result so this is actually the result computed by F that's how many times line 29 executed and finally I'm printing out the ratio of this result to the previous result so you can see here for two thousand the result is four million and that's four times the previous result which for 1000 was 1 million that ratio is printed here why is the ratio for what you can see is each time I double the size of the input I'm quadrupling the amount of work that's performed you can develop an intuition for that by looking at the square and thinking about what happens when the input value is 8 well I'm gonna get an 8 by 8 square what happens then when I increase that to 16 well now I have a 16 by 16 square and note that I haven't just doubled the size of the square I've actually got three extra things so we're up now to four times the size of the square so when we double the input we quadruple the square of that input this kind of analysis is helpful to develop intuitions for geometric series as well let's first look at the flat pack version where my inner loop is bounded by I by looking at the numbers you can see that our intuitions are correct note that we're not printing once for each value of I and J we're doing it twice but the ratio between sizes is 2 so whenever I double the size of the input I'm actually just doubling the amount of work I'm performing and this is characteristic of a linear time function now let's go back to our inner loop and adjust the bound to be in instead of I and let's run the code what we've got here is a logarithmic number of iterations of I and a linear amount of work for each of those iterations so this is n times the log of n this is linearithmic what do our experiments look like well you can see that the ratio between iterations is a little bit bigger than 2 and this is characteristic of linearithmic execution you can also see that the impact of the log factor gets smaller for larger input sizes as in becomes larger log n becomes insignificant so we've seen two techniques for understanding loops the first technique is to simply put a print statement in the innermost loop and then watch how many times it gets printed the second technique is to instrument the code to count how many times the inner loop body executes then you can compare the results and print them out the way I'm comparing results is quite simple note that I have variable min and Max min is my initial size 4n Max is my ultimate size for n I'm first running F on the minimum count then I'm going to double that so initially starting with twice the men I'm going to go up to the max each time doubling the size of in and what I'm computing here is simply the result of the function f and I'm going to print out that result plus the ratio of this to the previous count so in order to accomplish this I need to update the previous count each time around the loop these techniques are great for developing intuitions about how program complexity increases as input size increases but does it really tell me anything about the speed of the code on my machine we could check that by looking at a clock and seeing how fast our code runs or doesn't run but the computer has a clock in it why can't we just use that of course we can use the clock in a computer we just need to instrument our code a little bit to record the begin time and the end time and compute the difference for this purpose we'll use a stopwatch class when we create a stopwatch it starts a timer and we can check the elapsed time by invoking this method here I can see how long the first call to F took this will return a floating-point number giving us the number of seconds I'll do this each time I invoke F first creating a new stopwatch and then checking the elapsed time we can then print the elapsed time and the ratio of this time to the previous time and all we need to do is store that previous time and update it each time around the loop let's see what we get in this case the numbers aren't really what I expect I'm getting zeros for the ratio I'm getting infinity for the ratio I'm getting seven I'm getting 0.5 these numbers don't seem to give a pattern at all what we're noticing here is that computers are really fast and a little bit unpredictable my computer's not just running Eclipse it's running a lot of other programs and those programs share the same processors therefore what we're seeing here are systems effects and they're really apparent when we use small input sizes so let's try some bigger inputs you can see that things settle down as we finally get to large enough numbers and if you look at the last four iterations you can see the ratio is pretty much right around 2 which is what we expect note that the number is never exactly 2 and that's because we're counting the time on the wall clock and those system variations we have in our machine are always gonna be there so we're always gonna see small variations but with large enough numbers we get pretty darn close the absolute numbers are interesting as well for an input size of 260 million looks like I executed the body of the inner loop about 7 billion times and how long did that take well it took about 4 seconds you can relate that to the previous iteration where I did almost exactly half that amount of work and it took about half the amount of time 2 seconds note that this is my linearithmic pair of loops the outer loop is being executed a logarithmic number of times the inner loop a linear number of times so that's in times log of n the results I get by instrumenting my code are really precise and you can see the linearithmic qua here you can see that I'm not really close to two and that gets lower and lower we get closer and closer to two as we increase our input size but the experimental results using the wall clock don't really bear that out there's just too much noise in the system to distinguish a factor of 2 point 0 9 5 and a factor of 2 point 1 if what I've said is true then we wouldn't expect to see a dramatic difference between this execution and the flat-pack execution where we bound the inner loop by eye let's see what happens well that was fast so you can see that in terms of the ratios at the precise level what I said was true we're close to 2 for the flat-pack but if you look at the absolute numbers there's a large difference you can see for the input size of 260 million I'm doing about 260 million iterations of the inner loop now that is half of what I expected why is it 1/2 well if you look at the case for a thousand it's becomes clear my upper bound on my loop is going to be 1,000 and the values of I are going from 1 up to any value less than 1000 by doubling so the maximum value I'm gonna have for I is less than a thousand it's actually going to be 512 so the values for I here are going from 1 up to 512 and that's why the result for a thousand is 10:23 and similarly for 260 million I'm getting about 260 million remember from my linear rhythmic loops I was getting 7 billion here 7 billions a lot more than 260 million and that's reflected in the time it takes for 260 million operations it's taking point 1 4 seconds but remember for 7 billion operations it was taking 4 seconds as a result of these shorter execution times there's even more noise in the ratio and this seems to never really stabilize on a specific number we can try going even higher and see what happens well it took a while but once I got up to about a minute it was pretty stable it seems like executing a hundred and thirty seven billion operations takes about sixty eight seconds on my machine half the operations half the time you can see that even at very large input sizes there's a fair amount of systems noise thus when possible it's really nice to zero in on the instrumented values which are much more precise so let's go back to smaller numbers and just walk through the variations if both loops are moving arithmetic aliy up to n I end up with a square and you can see here that when I double the input size the result is quadrupled what do we expect to happen if I increment my loops by two instead of one well I should get about half the number of rows and half the number of columns so that would be a quarter of the size and I would expect the absolute numbers to decrease accordingly so here I'm taking about half a second for my 30 mm M put let's see what happens if I increment each of these by two instead of by one and indeed you can see the square is a quarter of the size and the absolute number that I'm getting is also about a quarter of what I had before so four instead of half a second we're down to point one something one thing that has not changed is the ratio of this iteration to the previous one there's a similar change if you look at the instrumented result that I've been computing that actually calculates precisely the number of iterations we're doing about a quarter the number now than we were doing before so I'm doing four times less work but note that that four times is ending of the input size and therefore the ratio of the amount of work is still quadrupling every time I double the size of my input this will hold no matter what the increment may be let's suppose instead of going up by two I go up by 20 well I'm still going to have 4 times the amount of work for double the size of input what if they're not the same well I'm still gonna have 4 times the amount of work for double the input everything changes if one of these were to become multiplicative and it actually doesn't matter which one I'll end up with far less work if I make them both multiplicative well now I'm gonna have a teeny tiny teeny tiny amount of work and in fact now my work is almost almost constant this is actually log times log is what's happening I have two logarithmic loops and so the amount of work is log times log which grows just a tiny bit faster than log experimentally you can see that no matter what the size of the input this is pretty much instantaneous as far as the computer is concerned the numbers are so small I can't even compute their ratios what I'm getting here is called not a number and it means that I'm essentially dividing by zero the computation is so fast it's beyond the precision of the timing instruments that we have available to us |
let's return to the square loop why am I getting a square here well I'm double iterating so for each value of I I iterate through J in x so the number of pairs IJ it's the square of n if I can do this for two loops I can do it for three let's put a third variable K into the mix and see what we get out well first of all note that my picture has gotten wonky its uh-oh it's just gone on and that's because I didn't put any kind of line breaks to visualize this effectively you really need three dimensional output because what we're doing here is a cube and in fact that's reflected in the results I get so for a thousand inputs I get the cube of a thousand or a billion and note that that's taking already just for a thousand inputs it's taking one second on my machine for two thousand inputs it's taking eight seconds on my machine what's the ratio between these eight and why does that make sense well let's think about it if I have some input in and that gives me a output when I double in I've got two times in there so what is that gonna be for a cubic function we'd expect the output to go to 2 to the third power whenever I double the input size why is that for two in going in I'm going to get two cubed and in cubed going out so 2 cubed is 8 thus we're seeing a ratio here of one problem to the next as I double the input size the time it takes goes up by a factor of eight this is characteristic of a cubic function note that in absolute terms my performance now is truly dreadful with an input size of only four thousand it's taking 30 seconds on my machine just like squares are related to triangles cubes are related to pyramids to create such a pyramid all I need to do is change the bounds of my inner loops to the induction variable value of my outer loop so here I'll bound J by I and I'll bound K by J before I run this code let's remember the absolute values that I was getting over here so for 4,000 inputs in the cube it was taking about 36 seconds I'll be back in 6 well actually it took 7 seconds but the point is made we're going about one-sixth the amount of time that's reflected in the results I'm getting I'm getting 1/6 of the value the geometry here is a little bit more complicated but if you think about a cube when you sort of slice it in one dimension and then slice it in the other you end up with a pyramid and that's 1/6 of a cube of course I can play this game in 4 dimensions as well well here's a 4 dimensional cube and you can see here the ratios now are 2 to the 4th which is 16 because I'm going in 4 dimensions for an input size of 200 my computers taking about 3 seconds what would it do for a triangular version of this code well it's taking about one twenty-fourth the amount of time it took for the four-dimensional cube so my 4 dimensional pyramid is one twenty-fourth of the size of my 4 dimensional cube for input size 200 it's taking a little less than a second on my machine you can see that the ratio between this four dimensional pyramid and the 4 dimensional cube is 24 by looking at the instrumented value this value here is about one twenty-fourth of the valley we got for the 4 dimensional cube why 24 well 24 is 6 times 4 and what we're actually getting here is factorial so 24 is 4 factorial why is that popping up well the exact mathematics is beyond the scope of this class but for the kinds of pyramids we're doing where each loop depends upon the bound of the previous loop you're going to see this kind of factorial reduction in the size of the pyramid relative to the cube the triangle is half the square the pyramid is 1/2 times 1/3 that's one-sixth of the cube and the 4 dimensional pyramid is 1/2 times 1/3 times 1/4 that's one twenty-fourth of the four dimensional cube |
all these dimensions are making my head hurt let's go back to two dimensions it's a nice simple case and we can reason in a very straightforward manner I think it's really important for you to experiment with these loops and actually see what they do for yourself try pasting in different things and seeing what happens you're also going to want to make predictions about the performance of recursive functions so how would we do that since recursive functions often return a value it may not be convenient for me to instrument the code to return the number of times the loop is executed instead I can use a field in my class such as this private field numb up and count using that field what I can then do is of course look at the field and remember the ratios just as I did before so here I'm doing a similar thing I'm just not using the return value of the function to count I'm instead using this num ops field it's important when you do this that you zero out the field every time you use it otherwise you will accumulate noise in the field by looking at the output of the function you can see that the ratio of two calls is doubling and therefore the function is more or less linear the wall clock isn't very useful here because the execution times are too short for loops I can play a trick when the execution times are too short I can just give larger and larger inputs but for recursive functions this might get us in trouble so if I run with a larger input I may get what's called a stack overflow exception stack overflows happen when I've made too many function calls the machine only allocates so much space for function calls and each function call takes a little bit of space so when the machine runs out you're done and you get a stack overflow exception so for recursive functions I need to keep my input sizes smaller because these input sizes are very small the wall clock isn't going to be useful what is this function computing well for an argument of one or less it just returns one otherwise it returns the previous call times in so if you think about it this is the factorial function our other favorite recursive function is of course the Fibonacci and I'll write the terrible Fibonacci and let's see how terrible Fibonacci performs well the Fibonacci of 20 is taking point oh one seconds the Fibonacci of 40 is taking more than half a second and if you remember the Fibonacci of 80 when we compute it in this terrible way it's gonna take up more than an hour if you look at the ratios here the ratio of 20 to 10 was 124 it took a hundred and twenty four times as long but look at 40 and 20 when I doubled the size of the input the output took 15,000 times longer this is increasing very very fast and this is the characteristic of an exponential execution and this is why this encoding of the Fibonacci is terrible strings are an important data type in almost every programming language and understanding the time it takes to perform various operations on strings is important as a programmer here I'm using string concatenation in Java to add one star to the result of a recursive call for N equals 0 this returns the empty string for n equal to 1 we'll get one star in front of the empty string for n equal to 2 we'll get one star in front of a string with one star so that's going to be length to 4 input 3 we're going to have one star in front of a string of length 2 so what we're computing here is simply a string of length in this function is using concatenation to do this and concatenation looks like it's similar to integer addition but it's not when Java concatenates two strings together it must allocate a new array to store that string and this does not take constant time it instead takes time proportional to the length of the result thus to correctly understand the number of operations in this loop we can't simply add one every time we do this addition we need to add the length of the result and when you do that you'll see that this code is quadratic in in not linear as you might expect this particular fact about strings has nothing to do with recursive functions the same also holds for a loop if I have a looping version of this code which is adding in one character to the result each time around the loop it's not doing a constant amount of work here it's doing amount of work proportional to the length of the result once I've written this as a loop I can crank up the upper bound to see what's happening what I want to do is see what happens to the wall clock just to verify that my hypothesis here about what concatenation is doing is correct so let's run it you can see that for 320,000 elements it took about six seconds whereas for twice that many elements it took 25 seconds that's a ratio of approximately four which is what we would predict if this loop work quadratic and since the loop is only executing a linear number of times this tells us that each iteration of the loop must be doing a linear amount of work thus we have a linear number of iterations a linear amount of work per iteration that's a square and we're getting the quadratic performance shown here what's the right way to produce a string of length in well this isn't it we'll talk about how to do this efficiently in a future lecture |
| 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
| 2D Square [3/19] |
01 |
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
This is quadratic: ~ N^2
| 2D Triangle [4/19] |
01 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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
| Recursive Factorial [16/19] |
01 |
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 |
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 |
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]
Exception in thread "main" java.lang.StackOverflowError at java.base/java.lang.StringBuilder.<init>(StringBuilder.java:124) at algs14.XCountingRecursion.f(XCountingRecursion.java:18)
| String Concatenation (Loop) [19/19] |
01 |
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
Revised: 2008/03/17 13:01