Indeed, good observation! The amortized runtime for N push_back will only be O(N) if the underlying array is resized to a constant factor > 1 times the require

Indeed, good observation! The amortized runtime for N push_back will only be O(N) if the underlying array is resized to a constant factor > 1 times the required size (e.g. doubling it each time it's full). When prefixing with reserve of the actual required size, then, as you say, the amortized runtime for the N push_backs will be O(N^2). I once investing a particularly slow routine to import csv to numpy-array of a million lines or so. It read csv lines in a numpy array, calling hstack for each new line, resulting in huge runtimes. Since then I have seen similar misuses of hstack and the like. When you do similar, it is important to resize (by hstack or whatever) to a constant factor > 1 times the required size. Don't forget to remember the current size, as the size of the underlying array is now the capacity.