CODEWITHSUNDEEP
javatime-complexity
Mike
Mike

Reputation: 7914

Time complexity of set in Java

Can someone tell me the time complexity of the below code?

a is an array of int.

Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < a.length; i++) {
    if (set.contains(arr[i])) {
        System.out.println("Hello");
    }
    set.add(arr[i]);
}

I think that it is O(n), but I'm not sure since it is using Set and this contains methods as well. It is also calling the add method of set.

Can anyone confirm and explain what the time complexity of the entire above code is? Also, how much space would it take?

Upvotes: 22

Views: 35469

Answers (2)

Alireza Fattahi
Alireza Fattahi

Reputation: 45475

Understanding HashSet is the key of question

According to HashSet in Javadoc,

This class implements the Set interface, backed by a hash table (actually a HashMap instance)...This class offers constant time performance for the basic operations (add, remove, contains and size)

A more complete explain about HashSet https://www.geeksforgeeks.org/hashset-contains-method-in-java/?ref=rp

So the HashSet insert and contains are O(1). ( As HashSet is based on HashMap and Its memory complexity is O(n))

The rest is simple, the main array you are looping is order of O(n) , so the total order of function will be O(n).

Upvotes: 0

hvgotcodes
hvgotcodes

Reputation: 120178

i believe its O(n) because you loop over the array, and contains and add should be constant time because its a hash based set. If it were not hash based and required iteration over the entire set to do lookups, the upper bound would be n^2.

Integers are immutable, so the space complexity would be 2n, which I believe simplifies to just n, since constants don't matter.

If you had objects in the array and set, then you would have 2n references and n objects, so you are at 3n, which is still linear (times a constant) space constraints.

EDIT-- yep "This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets."

see here.

Upvotes: 24

Related Questions