What is the time complexity of retainAll and removeAll of ArrayList in Java.

Question

As far as I can tell it is O(n^2) or is it ?

/**
     * Retains only the elements in this list that are contained in the
     * specified collection.  In other words, removes from this list all
     * of its elements that are not contained in the specified collection.
     *
     * @param c collection containing elements to be retained in this list
     * @return {@code true} if this list changed as a result of the call
     * @throws ClassCastException if the class of an element of this list
     *         is incompatible with the specified collection
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if this list contains a null element and the
     *         specified collection does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>),
     *         or if the specified collection is null
     * @see Collection#contains(Object)
     */
    public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true, 0, size);
    }

    boolean batchRemove(Collection<?> c, boolean complement,
                        final int from, final int end) {
        Objects.requireNonNull(c);
        final Object[] es = elementData;
        int r;
        // Optimize for initial run of survivors
        for (r = from;; r++) {
            if (r == end)
                return false;
            if (c.contains(es[r]) != complement)
                break;
        }
        int w = r++;
        try {
            for (Object e; r < end; r++)
                if (c.contains(e = es[r]) == complement)
                    es[w++] = e;
        } catch (Throwable ex) {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            System.arraycopy(es, r, es, w, end - r);
            w += end - r;
            throw ex;
        } finally {
            modCount += end - w;
            shiftTailOverGap(es, w, end);
        }
        return true;
    }

Answer 1

Assume that our ArrayList<T> has n elements, and Collection<?> has r elements.

The answer depends on the timing of c.contains(es[r]) check, as implemented in the subclass of Collection<?>:

• If c is another ArrayList<?>, then the complexity is, indeed, quadratic O(n*r), because c.contains(es[r]) is O(r)
• If c is a TreeSet<?> then the time complexity becomes O(n*log₂r), because c.contains(es[r]) is O(log₂r)
• If c is a HashSet<?> then the time complexity becomes O(n), because hash-based c.contains(es[r]) is O(1)

Answer 2

Removing an element from ArrayList takes O(N) time, because you have to shift all the elements after it toward the start to fill the gap you create.

retainAll and removeAll, however, do not use that procedure to remove each element. They are written to do all the required shifting during one pass through they array.

As they traverse through the array, elements to be retained are moved forward across the gap created by any removals, shifting the gap toward the end of the array. Elements to be removed are ignored, causing the gap to grow.

Since this only takes one pass through the array, no matter how many elements you have to remove, these methods work in O(N) time as well, if the reference collection can do contains() in O(1).