In article <UTC200101161350.OAA141869.aeb@ark.cwi.nl>,
Andries.Brouwer@cwi.nl writes:
>
> I am afraid I have missed most earlier messages in this thread.
> However, let me remark that the problem of assigning a
> file descriptor is the one that is usually described by
> "priority queue". The version of Peter van Emde Boas takes
> time O(loglog N) for both open() and close().
> Of course this is not meant to suggest that we use it.
>
Fascinating ! But how is this possible ? What stops me from
using this algorithm from entering N values and extracting
them again in order and so end up with a O(N*log log N)
sorting algorithm ? (which would be better than log N! ~ N*logN)
(at least the web pages I found about this seem to suggest you
can use this on any set with a full order relation)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Tue Jan 23 2001 - 21:00:14 EST