# Understanding execution time in nested loops

I have the following simple code

finalList = {};
For[i = 1, i <= myN - 3, i++,
For[j = i + 1, j <= myN - 2, j++,
For[k = j + 1, k <= myN - 1, k++,
l = RandomInteger[{k + 1, myN}];
AppendTo[finalList, {i, j, k, l}];
]
]
] // Timing


for some value of myN I obtain the following execution times

30 0.056
40 0.356
50 1.436
60 4.296
70 12.083
80 43.012
90 116.903


that grow much faster than N^3 (it's about N^6 for the first point and it is increasing for the last two points), and I cannot understand why.

Any insight of why this happens?

-
It is good to add one sentence what you code is eactly doing. People here don't remember anymore what nested Fors are doing :). p.s. Take a look at \$3.2 about AppendTo performance. You may also be interested in alternatives to procedural loops. – Kuba Mar 28 '14 at 11:40
Don't use AppendTo, it is very very slow use Sow and Reap. And yes as @Kuba hinted at don't use For loops. – Matariki Mar 28 '14 at 11:45
At the end: Tuples, Subsets and friends are quite fast when creating similar lists. – Kuba Mar 28 '14 at 11:47

To demonstrate the time saving using a linked list instead of AppendTo :-

time1[myN_] := First@Timing[
finalList = {};
For[i = 1, i <= myN - 3, i++,
For[j = i + 1, j <= myN - 2, j++,
For[k = j + 1, k <= myN - 1, k++,
l = RandomInteger[{k + 1, myN}];
AppendTo[finalList, {i, j, k, l}]]]]];

time2[myN_] := First@Timing[
finalList = {};
For[i = 1, i <= myN - 3, i++,
For[j = i + 1, j <= myN - 2, j++,
For[k = j + 1, k <= myN - 1, k++,
l = RandomInteger[{k + 1, myN}];
finalList = {finalList, {i, j, k, l}}]]];
finalList = Partition[Flatten@finalList, 4]];

ListLinePlot[
{Map[time1, {30, 40, 50, 60, 70, 80, 90}],
Map[time2, {30, 40, 50, 60, 70, 80, 90}]},
InterpolationOrder -> 2, PlotStyle -> Thick]


-
Thanks, time2 is now much similar to a cubic function in the size myN. It's just that is very strange to make a function just to do one thing, but then it is so slow that is better to not use it! – psmith Mar 28 '14 at 13:09
Probably ListLogPlot[%, Joined -> True] in order to see both traces? – rhermans Mar 28 '14 at 13:49