Hacker News Reader

Could you explain why adding to the end of an array results in O(n^2)? From what I can find, it appears to be O(1). If you increase the size of the array by 1 each time and copy the old array elements over, wouldn't that be O(n) to copy the array plus the additional add, O(n+1) which is just O(n)?

View on HN

Could you explain why adding to the end of an array results in O(n^2)?

If an operation does that n times, then it's O(n^2). It's very common for self taught programmers to write operations that do the naive addition many times. There have been entire consulting trips caused by basically that, including, so I heard, the one that brought a consultant into the Chrysler C3 project and sparked the invention of Extreme Programming.

Reply on news.ycombinator.com