Bill Atkins  <NOatkinwSPAM@rpi.edu> wrote:
+---------------
| rpw3@rpw3.org (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

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607