CODEWITHSUNDEEP
javaperformancedata-structuresjava-streamhashset
zonyang
zonyang

Reputation: 878

What is the time complexity of stream filter obtained from HashSet?

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
...

what is the time complexity of below operation? O(n) or O(1)?

set.stream().filter(e -> e == 1).findFirst();

Upvotes: 2

Views: 799

Answers (2)

Grzegorz Piwowarek
Grzegorz Piwowarek

Reputation: 13783

It's O(n) - after you create a Stream instance, you are no longer operating on a HashSet, but on a Stream that goes over all elements of the source Set.

It's a lazy linear sequence where all elements are visited one by one - hence O(n)

Upvotes: 1

Youcef LAIDANI
Youcef LAIDANI

Reputation: 59960

You can understand it better if you see it from another side, your solution is same like this :

for(Integer i : set){
    if(i == 1){
        break;
    }
}

So it is O(n) because it loop over all the set, and check one by one, if the condition is correct return the value else continue until n elsement

Upvotes: 1

Related Questions