title: Resizable Array and Amortized Runtime
body: <p>"Therefore, inserting N elements takes O(N) work total. Each insertion is O(1) on average, each though some insertions take O(N) time in the worst case." This quote is found in Cracking the Coding Interview. I kind of understand this statement even though a little thing about it is irking me. The amortized insertion is O(1) on good days. This simply means that when the resizable array doesn't need to resized, then to insert something is simply O(1). That is clear. But, on a bad day, when we run out of space, we would need O(N) to insert that extra element. However, I don't agree with the statement above when it says some insertion take O(N) in the worst case. Shouldn't it say, ONE insertion take O(N) in the worst case.</p>
  
  <p>To make this more clear, here's an example of what I'm saying.</p>
  
  <p>Say we have a resizable array, but we that array is size 4. Let's now say to insert 5 elements, we would have O(1), O(1), O(1), O(1), but then once we get to the last element, we would have to copy all these guys into a new array and this process would give us a cost of O(N). </p>
  
  <p>Can someone please clarify this for me. I don't understand why the book says some cases would take O(N) when when only need to copy all the elements into a new array one time when we run of of space in our old array. </p>