>>> Union-find structures I assume?
>>
>> Actually, something much more complicated than that.
>
> Intersting, what was it, I'm curious? The only other algorithm with that
> complexity I can think of off the top of my head is an MST algorithm.

An optimisation algorithm for logic programming.

> In that case, however, you may be further interested to know that the
> standard union-find algorithm also has inverse Acermann complexity. Thus
> there's an even simpler example of something with that "odd" complexity.

That's really odd. The Ackermann function is an ad hoc function with 
arbitrarily-chosen coefficients which was thrown together to prove a 
point. Why it should /ever/ occur in real life is beyond me...

Post a reply to this message