Regarding the time complexity of ABC 277 Ladder Takahashi

Правка en4, от 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 ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Girus 2022-11-15 08:15:17 3 Tiny change: 'ty reduce O(N) on a' -> 'ty reduce to O(N) on a'
en3 Английский Girus 2022-11-15 08:14:55 4 Tiny change: 'exity for aforement' -> 'exity for the aforement'
en2 Английский Girus 2022-11-15 08:14:34 94
en1 Английский Girus 2022-11-15 08:13:59 524 Initial revision (published)