CODEWITHSUNDEEP
pythonlistsetbig-ocomplexity-theory
Xazy
Xazy

Reputation: 9

Asymptotic complexity of converting list to set in Python

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?

Upvotes: 0

Views: 163

Answers (1)

Bastian Schiffthaler
Bastian Schiffthaler

Reputation: 268

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.

Upvotes: 1

Related Questions