What's the complexity of the concat strings operator in OCaml?

Question

What is the complexity of str_A ^ str_B in OCaml ?

Could it be anything other than `O(n)` (assuming a reasonable implementation)? You allocate a new string, copy `str_A` to it, then copy `str_B` to it. — glennsl, Jun 10 '22 at 13:22
If strings were implemented as radix trees or something it could get more interesting though... — glennsl, Jun 10 '22 at 13:34
It might be O(n^2) in a language like C that doesn't keep track of the length of a string for you, but that's not the case with ocaml. — Shawn, Jun 10 '22 at 17:05
I’m not sure why this question got downvoted. It is focused (it even has a bunch of relevant tags!), clear, pleasantly concise, of practical interest to most programmers, the answer is not obvious (considering that plain character arrays are not the only way to implement strings, see e.g. [ropes](https://en.wikipedia.org/wiki/Rope_%28data_structure%29)) and is not even given by [the documentation](https://ocaml.org/api/String.html) (which says nothing about time complexities nor about the implementation of strings). — Maëlan, Jun 10 '22 at 22:34
@Shawn That would still just be O(2n), not O(n^2). It would iterate over the string twice (2 * n), not iterate over the whole string for every character in the string (n * n). I can't even imagine an implementation that would be O(n^2) without throwing away most of the work. — glennsl, Jun 11 '22 at 10:18
@glennsl in Haskell for instance, strings are character *lists*, so a naive implementation of concatenation can easily exhibit a O(n²) complexity (or overflow the stack…). Of course, standard library authors know better. — Maëlan, Jun 11 '22 at 14:11

score 6 · Accepted Answer · edited Sep 01 '23 at 01:48

It's O(n). Here's the source code of the function:

let ( ^ ) s1 s2 =
  let l1 = string_length s1 and l2 = string_length s2 in
  let s = bytes_create (l1 + l2) in
  string_blit s1 0 s 0 l1;
  string_blit s2 0 s l1 l2;
  bytes_unsafe_to_string s

The function adds the length of the two strings, allocates a new buffer using that length, and then copies both the input strings into it.

In some languages, the runtime optimizes repeated string concatenations (for example several JavaScript implementations), but I don't believe OCaml does this based on this benchmark.

What's the complexity of the concat strings operator in OCaml?

1 Answers1