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...
- nick > On 23 Jan 2021, at 17:37, Marco Antoniotti <marco.antonio...@unimib.it> wrote: > > > Rrrrright. > > Yep. The question was stupid. Sorry. > > MA > > >> On Sat, Jan 23, 2021 at 6:35 PM Elias Mårtenson <loke...@gmail.com> wrote: >>> 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. > > > -- > Marco Antoniotti, Associate Professor tel. +39 - 02 64 48 79 > 01 > DISCo, Università Milano Bicocca U14 2043 > http://bimib.disco.unimib.it > Viale Sarca 336 > I-20126 Milan (MI) ITALY
