Confusion about time complexity with hash maps

Question

On leetcode I find it is common to "ignore" the worst-case time complexity involving hash maps. I thought in software interviews that it was standard to assume "worst case" as they often do. Below is my solution to a simple problem. The problem is to find the first non repeating char in a string. I understand that hash maps are on average O(1) lookup.. but when iterating over the string, and looking up the hash map, why is the time complexity not O(N^2) and instead is O(N)?

#include <unordered_map>

class Solution {
public:
    unordered_map<char, int> m;
    
    int firstUniqChar(string s) {
        for(char c : s) {
            m[c]++;
        }
        for(int i =0; i < s.length(); i++) {
            if(m[s[i]] == 1) {
                return i;
            }
        }
        
        return -1;
    
    }
};

Quimby Quimby · Accepted Answer · 2020-11-22T19:19:42

It is on average O(N) because hash map is on average O(1) per lookup and you do O(N) of them.

On average means by averaging over all possible inputs. That means there might exists an input array that breaks a particular hash and achieves O(N) or much worse on every lookup.

Worst-case is heavily implementation specific - e.g. hashing into buckets depends on how are elements stored in each bucket. If they are in a simple list, then lookup is O(<duplicates>), binary tree will bring that down to O(log<duplicates>). There might also be a difference between searching for keys present and missing.

Also there is a big assumption that all hashed containers can grow with the number of elements stored. I.e. keeping the occupancy of buckets low.

It does not hurt to mention their worst-cases in interviews, it demonstrates you know they can have limits.

Confusion about time complexity with hash maps

2 Answers