1

Let's say i have a nested List which contains n^2 element in it and also i have a HashMap which contains n^2 keys in it. I want to get common elements between the list and hashmap with using retainAll() function. What is the time complexity of retainAll() in this case?

List<List<Integer> list = new ArrayList<>();
Map<List<Integer>, Integer> hashmap = new HashMap<List<Integer>, Integer>();
list.retainAll(hashmap);

To get the commons,i'm using this loop but it has n^2 complexity.

List<List<Integer>> commons = new ArrayList<>();

    for (int i = 0; i < list.size(); i++) {
        if (hashmap.get(list.get(i)) != null) {
            commons.add(list.get(i));
        }
    }

Also if you have an algorithm which has better time complexity to get intersection of them, i need it.

EDIT : Actually the problem is , i have a list of integers size of n . But i divided that list into sublists and sublists count became n^2. Since i want to find out that hashmap contains every sublist as a key in it, i used n^2 in question. But it's too big according to my whole project. I'm searching complexity decreasing ways.

Naragoza
  • 91
  • 1
  • 7
  • Seems like a duplicate of [this](https://stackoverflow.com/questions/24754881/what-is-the-time-and-space-complexity-of-method-retainall-when-used-on-hashsets) – Guilherme Schaidhauer Castro Jan 14 '21 at 23:02
  • @GuilhermeSchaidhauerCastro I checked it before this post but I couldn't be sure it's the same. HashSet and HashMap may cause difference. Also i couldn't get the answer clearly. – Naragoza Jan 14 '21 at 23:09

1 Answers1

2

Well, I mean if you have n^2 items in the list then the complexity is O(n^2), although this a really weird thing to say. Usually n is the size of the collection, so the time complexity of retainAll is consider O(n).

It's impossible to have an algorithm that produces a better time complexity for this, as far as I can think of. You have to iterate the list at least once...

What you can do is switch your data structure. Read more: Data structures for fast intersection operations?

Rubydesic
  • 3,386
  • 12
  • 27
  • Thank you @Rubydesic. Actually the problem is , i have a list of integers size of n . But i divided that list into sublists and sublists count became n^2. Since i want to find out that hashmap contains every sublist as a key in it, i used n^2 in question. But it's too big according to my whole project. I'm searching complexity decreasing ways. – Naragoza Jan 14 '21 at 23:28