Due to lack of hashing, we need to do a “manual” union. Currently, it’s done by sorting and deleting duplicates. Sorting requires
comparisons. However, because the states themselves are length
, each comparison is
. So, the sorting is
. We do
events, so the total time is
. So, the time is expected.
In order to eliminate the sorting, we need to hash the elements. However, without occasional direct comparisons, we might run into hash collisions (which is why std::unordered_set takes a comparator struct as a template argument).