5 ms·
> why adding to the end of an array that doubles when it expands is O(n) amortized Not to be overly nit-picky here, and technically O(n) is correct as well (it
by lorenzhs 10y ago
> why adding to the end of an array that doubles when it expands is O(n) amortized
Not to be overly nit-picky here, and technically O(n) is correct as well (it's also the un-amortized worst case of insertion), but you probably meant to say that the amortized time is O(1), or θ(1) to be even more precise :)
- stcredzero 10y agoto be even more precise :) Or, you should demonstrate the self awareness to realize that you're just playing with the ambiguity of English in a hastily written comment. Exercise: in what precise context would time/space complexity be O(n), and in what precise context would it be O(1)? (Though the emoticon is probably an indicator that you already knew all this.)
- lorenzhs 10y agoI'm well aware how to analyze a dynamically growing array (each insert "pays" for two moves in the future), but I'm not sure what you're getting at. The amortized complexity of appending an element to the end is θ(1), worst-case non-amortized θ(n) when the growing needs to happen.
- stcredzero 10y agoThen do that N times. Then re-read the text and think of the context being discussed.