**Challenges**
• Asked 9 months ago by Jake from AlgoDaily

oh my gosh

haha what's up?

Why the solution using `Set`

is `O(n)`

?

There are 2 inputs so we should have `n`

and `m`

, no?

Assume that `n`

is the size of *nums1*, and `m`

is* nums2*. We traverse nums2 with `filter()`

and in every iteration we traverse nums1 with `has()`

. So shouldn't it be `O(m*n)`

?

Correct me if I'm wrong, but I think I've found the answer:*"Set objects must be implemented using [mechanisms] that, on average, provide access times that are sublinear on the number of elements in the collection"*

If I understand correctly, implementing `Set`

with *Disjoint Sets* data structure, for example, the complexity of `has()`

is `O(1)`

. Constructing the set from *nums1* with the `Set`

constructor is `O(n)`

.

(Look here for more details).

So we have *m* operations of `O(1)`

after constructing the set from *nums1*. That gives us complexity of `O(n+m)`

, which is roughly `O(n)`

assuming that *n* is the larger input.