4 ms·
I'm not totally sure what you mean by "dynamic array", but the vector algorithm for insertion (which you should probably at least include, if by "dynamic array"
by alecbenzer 13y ago
I'm not totally sure what you mean by "dynamic array", but the vector algorithm for insertion (which you should probably at least include, if by "dynamic array" you were implying a more naive insertion scheme) is O(1) amortized.
- gizmo686 13y agoIf we are talking about the same thing (an array that you reallocate to twice its size when you fill), then it has an amortized O(1) time to append something to the end. If you want to insert something in the beggining, you will need to move n elements down an index. A random location will average n/2, which is O(n)
- alecbenzer 13y agoAh, true. I guess the chart should probably distinguish between arbitrary index insertion and appending.
- dllthomas 13y agoThough with a gap buffer, you can have O(1) to insert/delete at some other point. Costs O(n) to move that point, though.