ArjoKar11_01's blog

Can using unordered map result in TLE?
By ArjoKar11_01, history, 3 months ago, In English

Help !!!

https://mirror.codeforces.com/contest/1926/submission/275328157 & https://mirror.codeforces.com/contest/1926/submission/275328315 both these code correspond to the same logic, the difference is just in using map and unordered map, But first one, which is done by using unordered map results in TLE. But why? As far as I knew unordered_map requires lesser TC w.r.t map. Kindly correct me if I am wrong.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ArjoKar11_01 (previous revision, new revision, compare).

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ArjoKar11_01 (previous revision, new revision, compare).

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The worst case time complexity of the operations on unordered_map is O(n).SO it will give you TLE.

You can check this out : https://mirror.codeforces.com/blog/entry/50626

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Using unordered_map on large amount of data will result in "blowing up" which increases the time complexity. There are already several blogs on this, might want to check this out

→ Reply