bug-gnulib
[Top][All Lists]

## Re: complexity of repeated use of m4_append

 From: Bruno Haible Subject: Re: complexity of repeated use of m4_append Date: Sun, 13 Jul 2008 12:49:57 +0200 User-agent: KMail/1.5.4

```> 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

```