Time complexity of this code? Very confused

Question

unordered_map<int,int> mymap;
        for(int i = 0; i < nums.size(); i++){
            mymap[nums.at(i)]++;
        }

        priority_queue <pair<int,int>> maxheap;
        for(auto it = mymap.begin(); it != mymap.end(); it++){
            maxheap.push({it->second,it->first});
        }

        vector<int> result;
        
        for(int i = 0; i < k; i++){
            result.push_back(maxheap.top().second);
            maxheap.pop();
        }

        return result;

I'm confused because on leetcode, the first for loop where I loop through and insert into map is counted as simply O(n) time. Shouldn't it actually be O(n^2)?? Insertion into a map is O(n) at worst case I thought.

I am confused why the first for loop is simplt O(n) time complexity

Answer 1

Internally unordered_map is implemented using Hash Table, the key provided to map is hashed into indices of a hash table which is why the performance of data structure depends on the hash function a lot but on average, the cost of search, insert, and delete from the hash table is O(1).