ra4o4ok's blog

Асимптотика функций std::map
By ra4o4ok, history, 9 years ago, In Russian

Ходят слухи, что функция count в std::map работает за линейное время от количества элементов. Правда это или нет?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

No, it is perfect O(logN) for each operation. Maybe you are confused by work of unordered_map that can make O(n) operations in worst case.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    what about some Meet-in-the-Middle problems, where map is getting Time Limit and lower_bound getting AC

    → Reply