Indeed complexity is O(n^2)
. For deeper explanation of how we arrived at O(n^2)
:
Pretend input is [1 2 3 4 5 6]
Outer loop iteration 1: answer == [ ]
, t == 1
Outer loop iteration 2: answer == [1]
, t == 2
Outer loop iteration 3: answer == [1, 2]
, t == 3
Outer loop iteration 4: answer == [1, 2, 3]
, t == 4
Outer loop iteration 5: answer == [1, 2, 3, 4]
, t == 5
Outer loop iteration 6: answer == [1, 2, 3, 4, 5]
, t == 6
Now sum the number of each inner loop iterations for each of the 6 outer loop iterations:
0 + 1 + 2 + 3 + 4 + 5 = 15
(5 + 0) + (4 + 1) + (2 + 3) = 15
(n/2) * (n - 1) = (n^2 - n)/2 -> O(n^2) (this is the tightest bound)
List<T> answer = new ArrayList<T>();
for (T t : self) {
boolean duplicated = false;
for (T t2 : answer) {
if (comparator.compare(t, t2) == 0) {
duplicated = true;
break;
}
}
if (!duplicated)
answer.add(t);
}
if (mutate) {
self.clear();
self.addAll(answer);
}
return mutate ? self : answer;
I argue that one can write her own algorithm for accomplishing the same thing but in O(n)
time, specifically using a Map
. First throw all the items into the Map
using the specified key, then iterate through all values in the Map
. Throwing items into Map
is O(n)
, iterating is also O(n)
, which equates to O(n)
(not O(2n)
since the growth is still linear). Not sure why Groovy developers didn't optimize, unless I'm missing something.