I think it depends on how set works under the hood.
At first, because there is only one for loop, one might think it’s only O(n).
But how does the `contains()’ method actually work? I have just read here and it says that set will internally iterate its elements and compare each element to the object passed as parameter.
Another way of making sure that there isn’t another for loop going on behind the scenes is by using a map. Because accessing an item requires O(1) time.(as far as I know)
I think it depends on how set works under the hood.
At first, because there is only one for loop, one might think it’s only
O(n)
.But how does the `contains()’ method actually work? I have just read here and it says that set will internally iterate its elements and compare each element to the object passed as parameter.
Another way of making sure that there isn’t another for loop going on behind the scenes is by using a
map
. Because accessing an item requiresO(1)
time.(as far as I know)So it could be that the
Set
solution is just as memory-efficient as the double-for
loop. I'd love to do a benchmark of this.If you do, please let me know what the results are!
Thanks!