Girus's blog

Regarding the time complexity of ABC 277 Ladder Takahashi
By Girus, history, 20 months ago, In English

Good evening all,

I am reaching out, as I had some questions about the editorial for ABC 277 problem C. The editorial for ABC 277 C — Ladder Takahashi states that the time complexity for the aforementioned problem is O(N * log (N)).

  1. Where is this logarithmic factor coming from ? Is this from the set and map data structures which take logarithmic time for insertion and search operation ?
  2. Would the time complexity reduce to O(N) on average if we were to use an unordered_map or unordered_set ?
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
20 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

YES and YES.

Personally prefer map/set over unordered_map/unordered_set in any case where logarithmic operation is not the bottleneck. Plus it's shorter to type map/set. Hash collision is another concern but it's not the issue for this problem.

→ Reply