Liliana Marie Prikler schreef op di 03-05-2022 om 22:04 [+0200]:
> > > [...].  If you do split your home in multiple
> > > profiles however, you will benefit from faster union builds,
> > > which
> > > themselves have quadratic complexity as a lower bound.
> > 
> > Instead of working around quadratic behaviour, could we just make
> > it
> > linear behaviour?  
> If you're really clever, you might find a way to get O(n log n)
> through
> sorting.  In fact, looking closer at union-build, it seems to already
> use hash tables, which would make much of the implementation O(n log
> n), but that's a very naive analysis at a time in which I shouldn't
> do
> too much complexity analysis.  Needless to say, you can't get better
> than sorting.

O(n lg n) is almost O(n) (logarithms grow slowly), seems nice.

Greetings,
Maxime.