Question 1What's the computational complexity of the Groovy unique() method?Question 2How could I have figured it out by myself? The unique() method is defined in the class DefaultGroovyMethods. The source code can be found here: org.codehaus.groovy.runtime.DefaultGroovyMethods. Can you point me to the piece of code which illustrates the answer to question 1?
What's the computational complexity of the Groovy unique() method?
complexity;groovy
As Lernkurve pointed out in the comments, the implementation given in Groovy's source code appears to be O(n^2).public static <T> Collection<T> unique(Collection<T> self, boolean mutate) {    List<T> answer = new ArrayList<T>();    for (T t : self) {                    // << Outer loop over each item        boolean duplicated = false;        for (T t2 : answer) {             // << Inner loop over each found item            if (coercedEquals(t, t2)) {                duplicated = true;                break;            }        }        if (!duplicated)            answer.add(t);    }    if (mutate) {        self.clear();        self.addAll(answer);    }    return mutate ? self : answer ;}The outer loop ensures that the time complexity is at least O(n), because it will grow linearly as the input list grows. Likewise, the inner loop taken by itself is O(n). For each item in the input list, it then loops over each item that it's registered into the answer list to see if that item is already contained. Put them together and you've got an O(n^2) function.As I pointed out in the comments, there are a few ways you might get better performance out of this, for large sets. If you're willing to spend a bit more memory, you can use a Hash set of some kind to register whether or not an element has already been included. These generally have an O(1) lookup time to check if the current item is unique to the list.Alternatively, sorting the input list (if it is sortable) with a good sort function (most of those included in a language's standard library will be O(n log n)) can help, assuming you don't care about the order of the unique output list. This way you can be sure that duplicate elements will always appear in sequence with each other, and it becomes trivial to reject them from the output.