Questions about complexity of some functions in various implementations.

[Elias Mårtenson]

On Sun, 24 Jan 2021 at 00:40, Marco Antoniotti <marco.antoniotti at unimib.it>
wrote:

> Hello everybody
>
> I remember from the trenches that LW implementation of INTERSECTION and
> UNION does not have (expected) linear time complexity.
>
> Before I go ahead checking the various implementations, does anybody know
> what is the time complexity of, at least, FIND, FIND-IF, POSITION and
> POSITION-IF for VECTOR inputs in various implementations?  That is, does
> anybody know whether these functions have at least O(lg n) time complexity
> in any of the implementations out there?
>

How would they be able to do that? A binary search on a vector is indeed
O(log n) but that assumes the vector is sorted. Also, you need a comparator
function, not just a test function to use it, so even if there was a way to
tell POSITION-IF that the input is sorted, the API for this function
wouldn't allow it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/pro/attachments/20210124/31804921/attachment.html>