On Wed, 23 Dec 2009, Martin McClure wrote:
Levente Uzonyi wrote:
I'd think that a hashtable of elements that are linked into a tree structure would also be an attractive implementation of a sorted set. Insert and delete time would be O(log n) but lookup time would be O(1).
I don't see the point here. Without a tree structure (just a list) it's O(1) for both.
How do you get O(1) for sorted inserts into a list? That's usually considered an O(n) operation. Or am I misunderstanding what you mean by list?
Well, just realized that you are thinking about a sorted set. The original idea was to create an ordered set. Levente
Regards,
-Martin
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project