Saurabh Pillai wrote:
Time complexity of getDuplicates method:
Let's assume that list has N elements.
- Collections.sort(input), O(N LogN)
- duplicates.add(a);, for HashSet add is constant O(1)
O(N LogN) + O(1)
= O(N LogN)
Sorry I miscalculated this. It should be,
- Collections.sort(input), O(N LogN)
- for loop, O(N)
-- duplicates.add(a);, for HashSet add is constant O(1)
O(N LogN) + O(N) + O(1)
= O(N(LogN + 1))
=
O(N LogN)