### Complexity

When you begin to program in OCaml, one of the first pieces of advice you encounter is to prefer the '`::`

' operator over the '`@`

' operator for list construction. The question is, does it matter? Even knowing that '`@`

' exhibits complexity $O(N)$ as opposed to $O(1)$ for '`::`

' should you care? I mean, how much of a difference can it make *really*?

The answer of course is yes. In practical terms, it matters. No, it really, *really* matters. Let's quantify it. Here's a version of the `range`

function that uses '`@`

'.

let range s e = let rec loop acc s e = if s >= e then acc else loop (acc @ [s]) (s + 1) e in loop [] s eAs an aside, you'll note that it's been written to be tail-recursive (so as to avoid inducing stack overflow).

Timing this function for building lists of $2^{10} = 1,024$ elements to $2^{16} = 65,536$ elements produces the following table:

n | time (s) |
---|---|

10 | 0.011243 |

11 | 0.047308 |

12 | 0.197137 |

13 | 0.866350 |

14 | 4.130998 |

15 | 22.769691 |

16 | 142.506546 |

Ouch! To build a list of just $65,536$ elements, the program takes over 2 minutes!?!

Ok, here's the version of `range`

that uses '`::`

' to build the list (and necessarily does a `List.rev`

on the result in order that the elements don't come out "back to front"):

let range s e = let rec loop acc s e = if s >= e then acc else loop (s :: acc) (s + 1) e in List.rev (loop [] s e)

And the timings for this one?

n | time (s) |
---|---|

10 | 0.000037 |

11 | 0.000097 |

12 | 0.000143 |

13 | 0.000324 |

14 | 0.002065 |

15 | 0.001195 |

16 | 0.005341 |

That is, this one builds the list of $65,536$ elements in just $5$ milliseconds!

Convinced?