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
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp

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.

- Raw text -