<div dir="ltr"><div dir="ltr">On Sun, 24 Jan 2021 at 00:40, Marco Antoniotti <<a href="mailto:marco.antoniotti@unimib.it">marco.antoniotti@unimib.it</a>> wrote:<br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hello everybody</div><div><br></div><div>I remember from the trenches that LW implementation of INTERSECTION and UNION does not have (expected) linear time complexity.</div><div><br></div><div>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?</div></div></blockquote><div><br></div><div>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.<br></div></div></div>