Interesting tidbit I found while brushing up on Big-O analysis – apparently some methods are O(a(m,n)) where a(m,n) is the inverse Ackerman function. It’s also sometimes written as a(n), if the two inputs are equal. This function does grow (so it’s worse than constant time) but it grows so slowly that it can almost be ignored.

a(n) will not grow larger than 5 for any number which can be written in the physical universe.

An example of an algorithm that demonstrates this is Chazelle’s algorithm for minimum spanning trees [pdf], which is O(e*a(e,v)) where e is the number of edges in the graph and v is the number of vertices. So it’s functionally O(e), but not quite.

Interesting, if useless.