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>

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

- Raw text -