> but only spend O(N lg N) time on copying the data around instead of O(N^2). O(n) time copying, with doubling the buffer, not O(n log n) It seems a bit count

> but only spend O(N lg N) time on copying the data around instead of O(N^2). O(n) time copying, with doubling the buffer, not O(n log n) It seems a bit counter intuitive, of course, that you can copy multiple times and have it still be O(n). The last copy will be n bytes. The second to last copy will be n / 2. The third to last, n / 4, etc. n + n/2 + n/4 + n/8 … = 2n You end up copying, roughly, 2n bytes across all the buffer resizes, which is O(n).