Re: [FWP] Ackerman

["Abigail" <abigail@foad.org>]

On Thu, Jun 28, 2001 at 10:54:59PM +0200, Christer Ekholm wrote:
> 
> Is Ackermann's function useful for anything?

Yes, but not so much the values of the function. Ackermann's function
turns up with some frequency in combinatorial problems, where we are
interesting the number of possibilities/configurations.

It also turns up in the complexity of some algorithms, and then as
the inverse Ackermann function. It's defined as:

    I(n) = m, where m is the smallest integer such that
              Ackermann (m, m) > n.

I(n) <= 4, (or 5, depending where you start counting) for all practical
values of n. There are algorithms out there that are superlinear, but
which are O (n I(n)).



Abigail

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe