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
