Re: complexity of repeated use of m4_append

[Bruno Haible]

> Eh? Even in that case it's O(n). Proof: Let n be the sum of lengths of the
> arguments. Let 1/q (0 < q < 1) be the growth factor. Then
>   - the number of byte copies from the argument strings to working memory is
>     exactly = n,
>   - the number of zeroed bytes and of copied bytes spent in reallocation is:
>       <= n*q + O(1) for the last reallocation,
>       <= n*q^2 + O(1) for the second-to-last reallocation,
>       ...
>       (at most log n / log q + O(1) reallocations).
>     So in total : <= n * (q + q^2 + ...) + O(log n) = n *q/(1-q) + O(log n)
>     = O(n).

Oops, that analysis was incorrect by a constant factor:
  - The number of copied bytes in reallocation is:
      <= n + O(1) for the last reallocation,
      <= n*q + O(1) for the second-to-last reallocation,
      ...
      (at most log n / log q + O(1) reallocations).
    In total : <= n * (1 + q + q^2 + ...) + O(log n) = n/(1-q) + O(log n)
  - The number of zeroed bytes in reallocation (assuming the entire memory
    block is zeroed before anything is copied into it) is:
      <= n/q + O(1) for the last reallocation,
      <= n + O(1) for the second-to-last reallocation,
      ...
      (at most log n / log q + O(1) reallocations).
    In total : <= n * (1/q + 1 + q + ...) + O(log n) = n/(q*(1-q)) + O(log n)

The O(n) result still holds.

Bruno