Jim Meyering wrote: > I've just changed xalloc's x2nrealloc to do n = 3n/2, rather than n *= 2,
Which means that the time needed for realloc() will grow by a factor of 1.7 on average. If it matters - haven't measured it -, I would suggest to use - n = 2*n for n < 1000000, - n = 3*n/2 for n >= 1000000, so as to not penalize the frequent small allocations. > - In the following implementation, nonzero sizes are doubled so that > - repeated reallocations have O(N log N) overall cost rather than > - O(N**2) cost, but the specification for this function does not > - guarantee that sizes are doubled. > + In the following implementation, nonzero sizes are increased by a > + factor of approximately 1.5 so that repeated reallocations have > + O(N log N) overall cost rather than O(N**2) cost, but the > + specification for this function does not guarantee that rate. How do you arrive at O(N log N) cost? I get O(N) + O(N/c) + O(N/c^2) + O(N/c^3) + ... = O(N) + O(log N) = O(N) where c is = 2 or = 1.5 respectively. Bruno
