Why is this code in functional style is slower than procedural style?

Question

I know that in Mathematica a functional programming style is often more efficient than procedural style programming using For loops. But the code shown below seems to be an exception, How to explain this?

del[ls_, k_] := Delete[ls, List /@ Range[k, Length@ls, k]]

max = 10^5;
r1 = Range[max];
For[i = 2, i <= Length[r1], i++, r1 = del[r1, i]]; // Timing

r2 = Range[max];
Do[r2 = del[r2, i], {i, 2, Length@r2}]; // Timing

r3 = Fold[del, Range[max], Range[2, max]]; // Timing

r1 == r2 == r3

Out:

{0.031200, Null}

{0.889206, Null}

{0.577204, Null}

True

Answer 1

In the first example, the list r1 is getting shorter each iteration, resulting in much fewer iterations overall:

max = 10^5;
r1 = Range[max];
c1 = 0;    
Timing[
 For[i = 2, i <= Length[r1], i++, c1++; r1 = del[r1, i]]; c1]

(*
==> {0.012426, 356}
*)

r2 = Range[max];
c2 = 0;
Timing[Do[c2++; r2 = del[r2, i], {i, 2, Length@r2}]; c2]

(*
==> {0.348965, 99999}
*)

c3 = 0;
Timing[r3 = Fold[(c3++; del[##]) &, Range[max], Range[2, max]]; c3]

(*
==> {0.417146, 99999}
*)