Q:

Time complexity and growth strategy of dynamic arrays

I was reading in More Exceptional C++ by Herb Sutter about growth strategy to be chosen when implementing a string. He lists the following:
1) Exact growth. In this strategy, the new buffer is made exactly as large as required by the current operation
Advantage: no wasted space.
Disadvantage: poor performance. This strategy requires O(N) allocations and an average of O(N) copy operations per char, but with a high constant factor in the worst case...
2) Fixed-increment growth. The new buffer should be a fixed amount larger than the current buffer
Advantage: little wasted space. The amount of unused space in the buffer is bounded by the increment size, and does not vary with the length of the string.
Disadvantage: moderate performance. This strategy requires both O(N) allocations and an average of O(N) copy operations per char. That is, both the number of allocations and the average number of times a given char is copied vary linearly with the length of the string.
However, control of the constant factor is in the hands of the String implementer.
note: characters are added to the string 1 by 1
Question 1 : How does the constant factor controlled in both? I din't Understand Herb's point here
Question 2: How will the Fixed increment be O(N), wouldn't depend on what the fixed size used is, if say its 100 chars, after the first resize, the next 99 insertions would be O(1), so why O(N) is considered?

A:

The string implementer gets to choose how big the fixed-size increment f is. So he has control over the constant factor in 2), but not in 1). Note that there is no claim of control over the constant factor in 1).
The cost per char would be O(N/f). I believe what Herb means is that f is fixed by the implementation, and hence is essentially a constant factor in the big-oh notation (i.e. it's dropped). However, the larger the f the smaller the big-oh constant factor is, and hence better performance (at the cost of more wasted space). So the implementer has to weigh those two factors when choosing f.

