List overview
Download

pro January 2021

pro@common-lisp.net

3 participants
1 discussions

Start a nNew thread

Questions about complexity of some functions in various implementations.
by Marco Antoniotti 23 Jan '21

23 Jan '21

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? All the best Marco -- 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

3 3