On 6/5/2012 12:34 AM, Orchid Win7 v1 wrote:
> On 04/06/2012 10:25 PM, Kevin Wampler wrote:
>> On 6/4/2012 2:12 PM, Orchid Win7 v1 wrote:
>>> I was reading a description for a computer algorithm. Get this, the
>>> authors claim that the time-complexity is proportional to the "inverse
>>> Ackermann function".
>>
>> 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.

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.

>
>> You could of course look a proof and read through it.
>
> I saw the proof. It's about 20 pages of dense formulas. Clearly I'd need
> to study it very carefully to figure out what the hell is going on...

Yeah, that proof does suck a little like that.

Post a reply to this message