On Sun, 24 Jan 2021 at 00:40, Marco Antoniotti <marco.antonio...@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.