why time complexity of pairs /Two sum using hashing is O(n) not O(n^2)

Question

i was going through a problem WAP to find all pairs of integers whose sum is equal to a given number

i check solution using hashing they say time complexity is O(n) but when i checked hashmap implementation, below program uses two iteration, one is using for another iteration is within contains method of hashmap so time complexity should be O(n^2) not O(n) Please correct if i am wrong

`static int getPairsCount(int arr[], int n, int k)
{
    HashMap<Integer,Integer> m = new HashMap<>();
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (m.containsKey(k - arr[i])) {
            count += m.get(k - arr[i]);
        }
        if(m.containsKey(arr[i])){
            m.put(arr[i], m.get(arr[i])+1);
        }
        else{
            m.put(arr[i], 1);
        }
    }
    return count;
}`

There’s no iteration in `O(n)` in a hash table. `contains` is `O(1)`. Java’s `HashMap` is a hash table. — Boris the Spider, Jan 25 '22 at 06:16
What do you mean, iteration? Only the for loop iterates over n things. Maybe you're surprised about hash tables and should read up on them. — clwhisk, Jan 25 '22 at 06:19
please check HashMap.class in java contains method uses `getNode(key) != null;` when you can see while loop for iteration — MhnSkta, Jan 25 '22 at 06:20
I think you are studying data structures and alghorithms and hence the question. Conceptually Hashtable uses a hash function to calculate the index of an array and starting from that index searches for the value in a LinkedList. Therefore worst-case performance for a contains is O(n) as the whole list might need to be traversed. This is just a conceptual answer - nothing to do with your code — J Asgarov, Jan 25 '22 at 06:20

MhnSkta · Answer 1 · 2022-01-26T09:15:46.213

-1

` final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

` this has iteration WHILE LOOP iterates the existing element to match the hash code

edited Jan 26 '22 at 09:15

answered Jan 25 '22 at 06:23

MhnSkta

73
8

2

Yes. This is hash collision resolution in a closed hashing hash table. I’m not sure you understand what this iteration is _over_. But regardless, the time complexity of `contains` in a hash table is `O(1)` - time complexity is not as simple as “looking for loops” I’m afraid. – Boris the Spider Jan 25 '22 at 06:29
but this .CONTAINS checks the existing hashcode present in hash table,once it got matched it returns true in above code inside for loop – MhnSkta Jan 26 '22 at 09:16

why time complexity of pairs /Two sum using hashing is O(n) not O(n^2)

1 Answers1