# What's the computational complexity of the Groovy unique() method?

Question 1

What's the computational complexity of the Groovy `unique()` method?

Question 2

How 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?

-
line 1031 seems to be where you need to look – jk. Jun 20 '13 at 8:35
@jk.: Two nested for-loops iterating over n, so O(n^2)? – Lernkurve Jun 20 '13 at 8:40
@Lernkurve Generally I'd expect you'd want to loop over the collection once, and register each in a hash table to note that it's already included. Slightly more memory intensive, but only O(n) to traverse the list a single time. Dunno if that's actually how Groovy handles it though. – KChaloux Jun 20 '13 at 13:00
@Lernkurve Upon actually looking at the code though, it looks like you're right... nested for-loops. :( – KChaloux Jun 20 '13 at 13:03
@KChaloux: Ok, from your comments I understand that the best implementation of unique() would have a complexity of O(n), but this particular Groovy implementation of unique() in revision 728bb83ec has a complexity of O(n^2). Thank you. – Lernkurve Jun 20 '13 at 13:54

## 1 Answer

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.

-