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