<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto">INTERSECTION on LW used to be O(n^2) but that was some years ago and I think it got fixed. I don’t have an implementation to hand...<br><br><div dir="ltr">- nick</div><div dir="ltr"><br><blockquote type="cite">On 23 Jan 2021, at 17:37, Marco Antoniotti <marco.antoniotti@unimib.it> wrote:<br><br></blockquote></div><blockquote type="cite"><div dir="ltr"><div dir="ltr"><div>Rrrrright.</div><div><br></div><div>Yep. The question was stupid. Sorry.</div><div><br></div><div>MA</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, Jan 23, 2021 at 6:35 PM Elias Mårtenson <<a href="mailto:lokedhs@gmail.com">lokedhs@gmail.com</a>> wrote:<br></div><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 dir="ltr">On Sun, 24 Jan 2021 at 00:40, Marco Antoniotti <<a href="mailto:marco.antoniotti@unimib.it" target="_blank">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>
</blockquote></div><br clear="all"><br>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">Marco Antoniotti, Associate Professor</span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">tel.</span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px;text-decoration:none;display:inline;float:none;white-space:pre"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">+39 - 02 64 48 79 01</span><br style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">DISCo, Università Milano Bicocca U14 2043</span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"></span><a href="http://bimib.disco.unimib.it/" style="font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">http://bimib.disco.unimib.it</a><br style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">Viale Sarca 336</span><br style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">I-20126 Milan (MI) ITALY</span><br></div></div></div></div>
</div></blockquote></body></html>