What is the space complexity of computing linkedlist intersection

Question

I am computing intersection of 2 linkedlists, where one linkedlists if of size 'n' and second is of size 'm'. The code below, stores the items of smaller linkedlist in a set. Thus space complexity is O(m), where m < n, aka, m is length of smaller linkedlist.

But, it is possible that 2 linked lists are equal, m = n. So is the complexity O(n) ?

public IntersectionAndUnionLinkedList<T> intersection(IntersectionAndUnionLinkedList<T> list) {
        final Set<T> items = new HashSet<>();

        Node<T> firstSmall = null;
        Node<T> firstBig   = null;

        if (size <= list.size) {
            firstSmall = first;
            firstBig = list.first;
        } else {
            firstSmall = list.first;
            firstBig = first; 
        }


        Node<T> n = null;
        for (n = firstSmall; n != null; n = n.next) {
                items.add(n.item);
        }

        IntersectionAndUnionLinkedList<T> intersectionlist = new IntersectionAndUnionLinkedList<>();
        for (n = firstBig; n != null; n = n.next) {
            if (items.contains(n.item)) {
                intersectionlist.add(n.item);
            }
        }

        return intersectionlist;
    }

Answer 1

Well in case m=n, O(m)=O(n), but it is safe to state that the memory complexity is O(m) since it's the only real factor.

On the other hand, a HashSet<T> can under extreme circumstances be less memory efficient: after all it uses buckets, the buckets can be filled in a bad way. It depends on the exact implementation of a HashMap<T>. Although one still expect linear memory complexity so O(m).