Time complexity of iterating through a map and incrementing the value

CodeChef-DSA-learners
,
1

let us say I’m looping through a vector and incrementing the count whenever a number is encountered, I’m using an ordered map for the purpose,
my question is what is the total TC of the loop is it O(n) or O(nlogn).

         map<int,int>mp;
         for(int i =0;i<N;i++){
            mp[i]++;
         }
2

Since each operation on loop must be constant time, iterating through N elements must be O(n) .

3

doesn’t ordered map take O(logn) for accessing elements?

4

The time complexity is O(NLog(N)) this is because when you are using map they are implemented in the form of trees hence each insertion takes log(N) time thus total it takes O(N* Log(N)) time.
The time complexity would have O(N) if you would have use unordered_map<> because they are implemented internally using hashing.
If you want to know more I think you can find interesting articles.
Hope this answers your query. :smiley:

Hey I have answerered in depth in this article:
Please refer this forum if you are interested

2 Likes
5

thank you, I had a bit of doubt in this and couldn’t find a satisfying answer in StackOverflow too now it’s clear :slight_smile:

1 Like
6

Well I am Happy that I could help you :smiley: