Questions about complexity of some functions in various implementations.

[Marco Antoniotti]

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/3c118e31/attachment.html>