7

Is there a Java collection with a complexity of O(1) and not O(n) for the addAll operation, or must I implement my own collection ? With a efficient linked list the Collection1.addAll(Collection2) operation should append the second collection to the first adding the first node of collection2 to the last of collection 1 and the others follow. But it' s not that I read into the documentation it seems to use an Iterator so I guess the complexity is O( collection2.size).

Is that right ?

kaizokun
  • 926
  • 3
  • 9
  • 31

2 Answers2

4

Even the optimization for linked lists can only work if you move items from one linked list to another.

You could build an own kind of collection, however, which has one more level of indirection, i. e. which contains a collection of collections. This way, adding whole collection is quite cheap, and so is iterating. Indexing or length determination can become quite expensive, however.

glglgl
  • 89,107
  • 13
  • 149
  • 217
  • thanks of course it's really depend on the case. For the length determination a simple addition of the two sizes could do the job I think. – kaizokun Jul 12 '16 at 09:41
  • @Kaizokun If it's only two. Maybe it will be more, if you design this class with maximum flexibility. – glglgl Jul 12 '16 at 09:48
  • of course each time I append a collection I add up the size :) – kaizokun Jul 12 '16 at 11:38
4

ArrayList is probably as good as it gets in this respect, but it actually depends on the supplied collection as well. The best-case complexity is O(1), but only if the supplied Collection's toArray() method also has constant complexity.

The System.arrayCopy() call that does the actual allocation is O(1), anyway is complicated, see below:

// java.util.ArrayList.addAll
// Oracle JDK 1.8.0_91
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray(); // O(?) <-- depending on other type
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew); 
    size += numNew;
    return numNew != 0;
}

There's some disagreement on whether System.arrayCopy is a constant-time operation. Some say no. Others suggest it is.

According to this benchmark I hacked together, it's somewhere in the middle. Copy Times stay pretty much constant up to about 100 array items, but grow linear from there on, I am guessing some kind of paging is involved there. So effectively, System.arrayCopy has linear time complexity unless the arrays are very small.

Community
  • 1
  • 1
Sean Patrick Floyd
  • 292,901
  • 67
  • 465
  • 588
  • thanks you, In my case the collection is a linked list ( a chained list I don't know how to say that in english) so the toArray Operation is O(n) I guess. – kaizokun Jul 12 '16 at 09:43
  • 1
    Are you sure about this? http://stackoverflow.com/questions/7165594/time-complexity-of-system-arraycopy claims something different. Furthermore I'm pretty sure `ensureCapacityInternal` is also in `O(N)`. – fabian Jul 12 '16 at 09:44
  • The first part is a source of religious wars, true. I'd argue that from a Java perspective, it's an atomic operation. There's disagreement here, but this answer supports my theory: http://stackoverflow.com/a/2772176/342852 – Sean Patrick Floyd Jul 12 '16 at 09:53
  • The second part is wrong. ensureCapacityInternal has a best-case complexity of O(1) and a worst-case of O(n), but the ratio of best to worst case is good enough to make the linear aspect negligible. – Sean Patrick Floyd Jul 12 '16 at 09:57
  • There is no argument for System.arrayCopy being O(1). It must loop over every item in the array to copy it. Just using memmove doesn't magically make it O(1) since memmove is not O(1) despite it being a single instruction in Java. If it were true that calling any C function from Java was O(1) then you could also say that any NP problem is in fact O(1): just write a C function that solves the problem and call it from Java! – Oli Oct 13 '19 at 17:53