import java.util.*;
import org.apache.commons.collections.*;

public class Bob {

    public static void main(String[] args) throws Exception {
        test(Integer.parseInt(args[0]));
    }
    public static void test(int n) {
        Collection a = new ArrayList();
        for(int i=0; i            a.add("bob"+i);
        }
        Collection b = new ArrayList();
        for(int i=0; i            b.add("bob"+i);
        }
        long t1 = System.currentTimeMillis();
        CollectionUtils.subtract(a, b);
        long t2 = System.currentTimeMillis();
        System.err.println("T" + n + ": " + (t2-t1));
    }

}

For an input of 10,000, both were around 550 msec. For 100,000 the ArrayList was 58000, while the LinkedList was 84000. Hardly scientific as I'm not repeating the test in the same run so could be missing out on JIT improving a second run, not running multiple times etc. My suspicion is that the ArrayList constructor checks to see if things are ArrayLists and does quick arraycopies, while the LinkedList constructor just sits and plods along. I retested by changing the input to LinkedLists from ArrayLists and the time doubled up to 102000. Of course when I try LinkedList passing in to the LinkedList variant, it goes up to 125000. Ah well.

Point of all that - apart from implying that more testing is needed - is that the collection type used might want to depend on the type of the 'a' variable.