> 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
