Asymptotic complexity of converting list to set in Python

Question

There's already a question regarding this, and the answer says that the asymptotic complexity is O(n). But I observed that if an unsorted list is converted into a set, the set can be printed out in a sorted order, which means that at some point in the middle of these operations the list has been sorted. Then, as any comparison sort has the lower bound of Omega(n lg n), the asymptotic complexity of this operation should also be Omega(n lg n). So what exactly is the complexity of this operation?

Converting a list to a set is still O(n). Printing it out is another operation. — quamrana
– quamrana, Commented Nov 1, 2019 at 10:19

Bastian Schiffthaler · Accepted Answer · 2019-11-01 10:19:13Z

1

A set in Python is an unordered collection so any order you see is by chance. As both dict and set are implemented as hash tables in CPython, insertion is average case O(1) and worst case O(N).

So list(set(...)) is always O(N) and set(list(...)) is average case O(N).

You can browse the source code for set here.

answered Nov 1, 2019 at 10:19

Bastian Schiffthaler

2681 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Xazy Over a year ago

Oops. Seems that the two convertions I had run somehow both returned sorted sets.

Collectives™ on Stack Overflow

Asymptotic complexity of converting list to set in Python

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related