Questions about complexity of some functions in various implementations.

[Nick Levine]

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.antoniotti at unimib.it> wrote:
> 
> 
> Rrrrright.
> 
> Yep.  The question was stupid.  Sorry.
> 
> MA
> 
> 
>> On Sat, Jan 23, 2021 at 6:35 PM Elias Mårtenson <lokedhs at gmail.com> wrote:
>>> On Sun, 24 Jan 2021 at 00:40, Marco Antoniotti <marco.antoniotti at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/pro/attachments/20210123/352086e9/attachment-0001.html>