JioFell's blog

What's time complexity of swap operator of 2 bitset?
By JioFell, history, 6 years ago, In English

In this problem(1070L - Odd Federalization), I used gaussian elimination (O(n^3)) but I have used bitset because I think it will be faster. Finally, I got AC (44701036) but I still don't understand all details of bitset's complexity. Thanks for reading my blog

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

See http://www.cplusplus.com/reference/algorithm/swap/. If you swap anything but two arrays, it's constant. That means even bitset or vector.

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Its O(1) always because it swaps iterators/doesn't actually copy the contents over.

So when you see (sz(a) < sz(b)) swap(a,b) for thing like merge small to large this swap is constant (or else it would not be nlogn overall)

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

    If I want to swap iteraters of 2 things a and b, I always use a.swap(b). But I can't use that way with bitset so I think it's O(n^3) without reducing by complexity of bitset. Tks you :3 :3

    → Reply
»
6 years ago, # |
  Vote: I like it -11 Vote: I do not like it

It's n/64 because data is stored insidebitset itself (like in an array but unlike in a vector)

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

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

→ Reply