Subject: Re: ANSI Common Lisp, Ch 3, Ex 3
From: (Rob Warnock)
Date: Thu, 02 Mar 2006 22:53:34 -0600
Newsgroups: comp.lang.lisp
Message-ID: <>
Bill Atkins  <> wrote:
| (Rob Warnock) writes:
| > Of course, the SORT occurs in both, and probably adds an amount
| > of around M * (log M). If you *really* wanted to speed this up for
| > large inputs, you'd figure out how to count and sort simultaneously,
| > e.g., maybe use some kind of clever balanced tree to insert into...
| I'm not sure you can beat O( M * log M ) for this - the sort operation
| puts a definite limit on the improvements you can make.  It's provable
| that you can't do better than N * log N for a general-purpose sort of
| of N elements.  Even if you insert each element into a tree, each
| insert would be O( log(M) ), repeated M times = O( M * log(M) ).

Don't you mean N * log(M)?  [N = input length, M = distinct kinds]
You have to do N searches/increments (with M inserts along the way), 
so if a search is log(M) then just building the tree(s) is N * log(M)
[plus O(M) for inserts].

Hmmm... For *really* large N [that is, N >> M], even if one could
get some tree-insert method down to N * log(M) that's still larger
than the hash-table-plus-sort, which is N + M + (M * log(M), which
is just O(N) [for N>>M].

So... "Never mind..."  ;-}


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607