Time complexity of set in Java

user_824210 0
Viewed 30314

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?

time-complexity java
2 Answers

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).

user_26480770
Related