Comment by kbsletten

Basically a linear array is packed tightly, so trying to put something in the middle, well first you have to move what's already there. Because it's packed tight, you end up having to move everything to the right one space from the right back to where you're creating a hole. Then you can put what you want in the middle. Sometimes you get lucky and you're adding something far to the right and don't need to shuffle many items first, but sometimes you need to put it on the very left and reshuffle the whole thing. You'll never have to shuffle anything twice, but is possible to end up shuffling everything once so we say it's O(N) which means never takes a crazy multiple of the number of items.