[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## 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