Python Sets Operations/Methods Time Complexity

Sets are unordered collection of items in Python, it doesn’t contain duplicate objects and also objects contained by a set need to be immutable. But Set itself is mutable. Because Sets are mutable meaning these can be changed there exist many methods for doing this, if your not aware of those methods/operations then see What are Set Methods/Operations in Python? article in which I’ve listed all of Python’s Set Methods.

Let’s first talk about What’s Time Complexity in Programming and Why you as a Python Developer need to care about this?

What is Complexity in Programming?

Complexity or O(n) is measurement of How many items needed to be considered for execute something. From daily life you can think this of as brushing your teeth, How many steps items you need to do brushing can be consider Complexity.(Quite Simple!!)

Why Programmer need to consider Complexity? Complexity needs to be considered by programmer while writing code as sometimes a piece of code need to be executed fast or sometime slower. For example – If your writing code for a Self Driving Car then you want code to be executed faster so that action(Turning Left/Right) can be taken quickly.

Defining Complexity Mathematically O(n)

  1. O(1) means in constant time – independent of the number of items.
  2. O(N) means in proportion to the number of items.
  3. O(log N) means a time proportional to log(N)

Basically any ‘O’ notation means an operation will take time up to a maximum of k*f(N)
where: k is a constant multiplier and f() is a function that depends on N

Table containing Sets Operations/Methods Complexity in Python

Just note that s, set1, set2 are Python Sets and v is any Data value in table below.

Set Operation/MethodExampleComplexity
Containmentx in/not in sO(1)
check ==, !=s != vO(len(s))
Is Subsetset1 <= set2O(len(set1))
Is Supersetset1 >= set2O(len(set2))
Unionset1 | set2O(len(set1) + len(set2))
Intersectionset1 & set2O(len(set1) + len(set2))
Differenceset1 – set2O(len(set1) + len(set2))
Symmetric Differenceset1 ^ set2O(len(set1) + len(set2))
Iterationfor v in s:O(N)

You May Also Like

Leave a Comment