From: Charles Krug <charles AT pentek DOT com>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: The meaning of O(n)...
Date: Mon, 26 Jan 1998 09:36:54 -0500
Lines: 26
Message-ID: <34CC9F86.166B3E3@pentek.com>
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>
NNTP-Posting-Host: mail.pentek.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

Heutchy wrote:

> > 2^n, n!, n^3, n^2, nlog(n), n, log(n), 1.
>
> At the risk of sounding like an idiot, isn't n! worse than 2^n?
>
> n! = 1 * 2 * 3 * 4 * ... * n-1 * n
> 2^n = 2 * 2 * 2 * 2 * ... * 2 * 2
>
> 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.

I dunno, I was working from memory . . . .

You're right, both by intuition, and by looking it up.  You correctly
guessed that I confused 2^n with n^n.

So I stand (or sit) corrected.

n^n is the complexity of multiplication of hypermatrices of order n in n
dimensions.  Sure, I do it all the time.  Yeah, right!

--
Charles Krug, Jr.