By “algorithm” I’m referring to more than just asymptotic complexity. Even so, as for “O(n^2)”… well, I didn’t analyze the code myself, but judging by Casey’s analysis (or even just by the symptoms), it seems quite likely that the time taken to input a character is at least O(n) in the number of characters entered so far (if not worse). That makes the total operation of entering n characters take O(n^2) time. Bob does seem to be referring to the total being O(n^2) rather than each character being O(n^2), since the reallocation strategy he mentioned as an example would similarly take O(n) per character. In that context, O(n^2) is less of a guess, more of a reasonable assumption given the observed performance characteristics. And it’s a reasonable aspect to point a finger at, because lowering the asymptotic complexity would be an essential part of fixing the performance problem. Not sufficient by itself, but pretty much necessary.