Re: [FWP] Ackerman

["Daniel S. Wilkerson" <dsw@digital-integrity.com>]

Abigail wrote:

> On Thu, Jun 28, 2001 at 10:54:59PM +0200, Christer Ekholm wrote:
> >
> > Is Ackermann's function useful for anything?
>
> 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

Oh yea, I forgot about that.  For example, the time complexity of the
Union-Find algorithm.  What if you have a bunch of sets of things, which
are all initially singleton sets.  The three operations you can perform
are: Union(i, j), which means merge two sets with names i and i, Find(i)
which means give me the name of the set containing element i.  (The sets
will have one of their members picked as its "name" arbitrarily with each
union.)  A theorem of Tarjan ("Fundamentals of Data Structures" Horowitz
and Sahni, p.256, Lemma 5.6):

    Let T(m, n) be the maximum time required to process any intermixed
sequence of m>=n Finds and n-1 Unions. Then
    k1 m alpha(m,n) <= T(m,n) <= k2 m alpha(m,n) for some positive
constants k1 and k2.

Here, alpha is their particular definition of the inverse of Ackermann's
function, which is in the book and I won't type in.  They say "For all
practical purposes we may assume log_2 (n) < A(3,4) and hence alpha(m,n)
<= 3."  So, its at most 3.

Daniel


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