Message-ID: <34CCCD26.5565@pobox.oleane.com>
Date: Mon, 26 Jan 1998 18:51:34 +0100
From: Francois Charton <deef AT pobox DOT oleane DOT com>
Organization: CCMSA
MIME-Version: 1.0
To: Charles Krug <charles AT pentek DOT com>
CC: djgpp AT delorie DOT com
Subject: Re: The meaning of O(n)...
References: <Pine DOT GSO DOT 3 DOT 96 DOT 980120190605 DOT 19121B-100000 AT bert DOT eecs DOT uic DOT edu> <34C8B7D1 DOT A19B36EA AT pentek DOT com> <34C98CE6 DOT 861 AT prodigy DOT net> <34CC9F86 DOT 166B3E3 AT pentek DOT com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Precedence: bulk

Charles Krug wrote:
> 
> Heutchy wrote:
> 
> > So the n! grows much faster.  n^n would be worse however.  I don't know
> > if there are any useful algorithms with O(n^n) though.
> 
> 
> n^n is the complexity of multiplication of hypermatrices of order n in n
> dimensions.  Sure, I do it all the time.  Yeah, right!
> 

By the way, n! and n^n are not very far from each other: by Stirling 
formula, n! is equivalent to sqrt(n) (n/e)^n. But again n! algorithm are 
rare enough (I suppose it is equivalent to solving a travlling salesman 
problem the hard way...).

Francois