Campbell Ritchie wrote:But insertion into an array list is usually regarded as amortised constant time
Campbell Ritchie wrote:Thank you, Martin; that would be linear time then. But why does ArrayList say amortised constant time, then?
JDK 13 doc wrote:The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
Paul Clapham wrote:If you use 1 (because copying the 64 elements is "blindingly fast" as Martin said) then you end up with O(1) -- the copying occurs only for powers of 2 so the cost is 1/2 + 1/4 + 1/8 + ... (That's what they mean by "amortized constant time").
Paul Clapham wrote:But if you use 64 then you end up with O(log N) -- the cost is 2/2 + 4/4 + 8/8 + ... (as the mathematicians say, the proof of this is "left as an exercise for the student").
Does ArrayList have an insert() method? If you use ctrl‑F‑insert, it finds the descriptions of the various add(...) methods.Martin Vashko wrote:. . . So, add operation is O(1). All the remaining ones (including insert) are O(n).
Campbell Ritchie wrote:Does ArrayList have an insert() method? If you use ctrl‑F‑insert, it finds the descriptions of the various add(...) methods.
Are you suggesting that the documentation comments might be mistaken? I am aware of errors in other documentation comments, particularly older ones.Martin Vashko wrote:. . . the Javadoc doesn't distinguish between the to add methods when discussing the amortized constant time. . . .
Campbell Ritchie wrote:Are you suggesting that the documentation comments might be mistaken? I am aware of errors in other documentation comments, particularly older ones.
We find the defendant guilty of imprecisionMartin Vashko wrote:. . . imprecise, not mistaken. . . . Supporting argument . . . remove(int index) . . . should be considered O(1) too. . . . .
Consider Paul's rocket mass heater. |