ArrayList and LinkedList

[Ana Smith]

I don't understand why inserting into an ordered ArrayList has a big O of O(n) and so does inserting into an ordered LinkedList.
I may be wrong but is it because you're just traversing through the list for both cases so that is why the time complexity is O(n)?

[Campbell Ritchie]

Please tell us where that information comes from. Are you sure they are correct?

Possible explanation for the first assertion:- Searching an ordered array list with binary search runs in logn time complexity, but inserting a value requires the elements “later” in the array to be moved. That moving runs in linear time complexity (=O(n)). The overall complexity is the same as the worst complexity of any of the component operations. But insertion into an array list is usually regarded as amortised constant time. In which case insertion at a certain search position found by binary search would run in logarithmic time.
Inserting into a linked list runs in constant time, but any searches will run in linear complexity; in fact a linear search will probably run faster than a binary search on a linked list. The linear time complexity will overwhelm the constant time of the insertion.

[Campbell Ritchie]

If youi use a linear search of the array list, that will run in linear time, but you would usually use a binary searh, so I still suspect there is an imprecision in your source.

[Martin Vashko]

Campbell Ritchie wrote:But insertion into an array list is usually regarded as amortised constant time

I might be mistaken, but I believe the amortized constant time only applies to the reallocation of the underlying array when the list grows. The new array is allocated in increasing size increments, which means that as the array grows, the reallocations get both more expensive and less frequent, converging to a constant value over time.

Insertion into a random position needs to shift all following elements, and this operation, although probably blindingly fast (there's the REP MOVS instruction, if I'm not mistaken), they will grow a wee bit longer as the array grows.

[Campbell Ritchie]

Thank you, Martin; that would be linear time then. But why does ArrayList say amortised constant time, then?

[Paul Clapham]

Just for example, when you add the 65th element to an ArrayList which has an underlying array of size 64, a new underlying array of size 128 is created and the 64 elements from the original underlying array are copied into it. (And then the new, 65th, element is added.)

So it depends on whether the cost of creating the new array is 1 or 64.

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").

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").

Unfortunately all of this analysis is way more than what Ana would have hoped for when they posted the question. The moral of the story is that the big-O notation must be applied to a specific algorithm. Just saying "inserting into an ArrayList" isn't sufficient -- you have to describe the algorithm that you're using. And then you have to analyze that algorithm to see how the size of the data affects it. That analyzing is what's been going on over the last several posts and it could go on longer.

[Martin Vashko]

Campbell Ritchie wrote:Thank you, Martin; that would be linear time then. But why does ArrayList say amortised constant time, then?

They speak about the growth of the ArrayList, not about inserting elements (emphasis mine):

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.

So, add operation is O(1). All the remaining ones (including insert) are O(n).

[Martin Vashko]

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").

I don't think this is what they mean by amortized constant time. Even when the copying does take more time as the arrays get longer, we still get O(1) per addition of one element:

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").

This this is the cost of adding N elements. If you want the cost of adding just one element, you get O(N/N) --> O(1).

[Campbell Ritchie]

Martin Vashko wrote:. . . So, add operation is O(1). All the remaining ones (including insert) are O(n).

Does ArrayList have an insert() method? If you use ctrl‑F‑insert, it finds the descriptions of the various add(...) methods.

[Martin Vashko]

Campbell Ritchie wrote:Does ArrayList have an insert() method? If you use ctrl‑F‑insert, it finds the descriptions of the various add(...) methods.

Damn!

No, it  doesn't. It has an add(E element), which adds to the end of the list, and add(int index, E element), which I somehow though was called insert.

ETA: Now, the Javadoc doesn't distinguish between the to add methods when discussing the amortized constant time. In the second paragraph I cited above, they link the amortized constant time characteristics to the growth of the buffer. I still maintain that add(E element) is O(1) and add(int index, E element) is O(n).

[Campbell Ritchie]

Martin Vashko wrote:. . . the Javadoc doesn't distinguish between the to add methods when discussing the amortized constant time. . . .

Are you suggesting that the documentation comments might be mistaken? I am aware of errors in other documentation comments, particularly older ones.

[Martin Vashko]

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.

I'd say imprecise, not mistaken. It just doesn't distinguish between two different add operations.

Supporting argument: if shifting elements was considered an O(1) operation by the documentation author(s), the remove(int index) operation should be considered O(1) too. Which it isn't.

[Campbell Ritchie]

Martin Vashko wrote:. . . imprecise, not mistaken. . . . Supporting argument . . . remove(int index) . . . should be considered O(1) too. . . . .

We find the defendant guilty of imprecision

But it would be useful to hear from OP where she read that adding to a sorted array list runs in linear time.