code_warrior's blog

Time complexity of dsu on tree
By code_warrior, history, 5 years ago, In English

I have recently read tutorial on dsu on trees in codeforces (Arpa's Blog).See this blog.(Specifically,the one titled easy to code in O(nlogn))I couldn't understand how the time complexity of it is O(nlogn).Please ,someone explain me!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

...

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

    But , one thing which I couldn't understand is that when we make the vector pointer point to the vector pointer corresponding to the largest set, is that taking O(n) time or O(1) time!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It's $$$O(1)$$$. Pointer is just a number that shows where the real vector is in the computer's memory. No data is being copied.

      → Reply