Questions about complexity of some functions in various implementations.
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
On Sun, 24 Jan 2021 at 00:40, Marco Antoniotti <marco.antoniotti@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.
Rrrrright. Yep. The question was stupid. Sorry. MA On Sat, Jan 23, 2021 at 6:35 PM Elias Mårtenson <lokedhs@gmail.com> wrote:
On Sun, 24 Jan 2021 at 00:40, Marco Antoniotti <marco.antoniotti@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
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@unimib.it> wrote:
Rrrrright.
Yep. The question was stupid. Sorry.
MA
On Sat, Jan 23, 2021 at 6:35 PM Elias Mårtenson <lokedhs@gmail.com> wrote:
On Sun, 24 Jan 2021 at 00:40, Marco Antoniotti <marco.antoniotti@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
participants (3)
-
Elias Mårtenson -
Marco Antoniotti -
Nick Levine