Time Complexity of strings

general
1

What is time complexity of inserting N strings of length L each in :

  • map
  • unordered_map
  • set
  • unordered_set
2

Map and set both have same complexity. I think both are implemented on trees only. (ordered one only)
Time complexity of insertion in map< vector< int > , int > ? - Codeforces
You can consider string as vector I guess

@ssjgz will explain in detail

3

I will try to explain the concept in accordance with best of my knowledge:
1.ORDERED MAPS:
Maps are generally implemented internally using red black trees(a kind of self balancing binary search trees. Please google it if you want to know in detail.) so the insertion,deletion and searching usually takes place in O(log(L)) per test case.
While considering the case of strings,if the strings are quite large then The time complexity would be O(size of string * Log(L)) per insertion .Try to imagine you are trying to insert an element into the binary search tree,While entering small string size doesn’t matter but when it comes to large strings size does matter as we usually compare at each level with our string.
generally,for N strings → O(Nlog(L)) or O(L*NLog(L))(for bigger string)

2)UNORDERED MAPS:
unordered maps are internally implemented using hash tables and thus AVERAGE TIME COMPLEXITY:O(1) per insertion time complexity.

Time complexity:O(N)(for N strings of length L)

ORDERED SETS are similar to ORDERED MAPS and UNORDERED SET is similar to UNORDERED MAP(i mean internal implementation are same).just the difference lies in the fact that in maps you try to use key value pairs but in sets you just can store the values .

3 Likes