4 Jun
2009
4 Jun
'09
2:32 a.m.
On Wed, Jun 3, 2009 at 7:43 PM, Daniel Peebles
An equality-based (n^2) nub works "fine" on infinite lists, whereas any O(n log n) sort-based nub must necessarily evaluate the entire list before being able to return the value.
No. You just need to keep anything seen so far in a container with O( log n ) insert/lookup times.
The original n^2 nub also returns the elements in the order of their first appearance rather than sorted order.
Where exactly did sorted order come in? D