Regarding the time complexity of ABC 277 Ladder Takahashi

Revision en4, by Girus, 2022-11-15 08:15:17

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 ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Girus 2022-11-15 08:15:17 3 Tiny change: 'ty reduce O(N) on a' -> 'ty reduce to O(N) on a'
en3 English Girus 2022-11-15 08:14:55 4 Tiny change: 'exity for aforement' -> 'exity for the aforement'
en2 English Girus 2022-11-15 08:14:34 94
en1 English Girus 2022-11-15 08:13:59 524 Initial revision (published)