CODEWITHSUNDEEP
c++arraysdictionaryvectorruntime
Kau
Kau

Reputation: 101

What is the runtime complexity of std::map in C++?

I'm still a little confused about what the runtime complexity is of a std::map in C++. I know that the first for loop in the algorithm below takes O(N) or linear runtime. However, the second for loop has another for loop iterating over the map. Does that add anything to the overall runtime complexity? In other words, what is the overall runtime complexity of the following algorithm? Is it O(N) or O(Nlog(N)) or something else?

    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        
        vector<int> result;
        map<int, int> mp;
        
        for (int i = 0; i < nums.size(); i++) {
            mp[nums[i]]++;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            int numElements = 0;
            for (auto it = mp.begin(); it != mp.end(); it++) {
                if (it->first < nums[i]) numElements += it->second;
            }
            result.push_back(numElements);
        }
        
        return result;
    }

Upvotes: 1

Views: 716

Answers (2)

Swan Toma
Swan Toma

Reputation: 146

Your second for loop runs nums.size() times, so let's call that N. Looks like the map has as many entries as nums, so this contains same N entries. The two for loops then of size N is N*N or N^2.

The begin and end functions invoked by map are constant time because they each have a pointer reference from what I can tell:

C++ map.end function documentation

Note if you do have two for loops, but the outer one is size N and inner one is different size say M, then complexity is M*N, not N^2. Be careful on that point, but yes if N is same for both loops, then N^2 is runtime.

Upvotes: 0

mipsc
mipsc

Reputation: 113

The complexity of a map is that of insertion, deletion, search, etc. But iteration is always linear.

Having two for loops like this inside each other will produce O(N^2) complexity time, be it a map or not, given the n iterations in the inner loop (the size of the map) for each iteration of the outer loop (the size of the vector, which is the same in your code as the size of the map).

Upvotes: 1

Related Questions