Search code examples
pythonsettime-complexityfrozenset

Complexity of converting a set to a frozenset in Python

What is the computational complexity of "freezing" a set in Python?

For example, does the second line in

a = {1,2,3}
b = frozenset(a)

require O(n) time? Or is it simply a "view" created in constant time?

Solution

  • b is not a view of a. You can check this via id:

    a = {1, 2, 3}
b = a

id(a) == id(b)  # True

b = frozenset({1, 2, 3})

id(a) == id(b)  # False

    Hence a change in b will not be reflected in a. You can, of course, test this yourself. Since frozenset takes an iterable as an argument, it must iterate over each argument. This is an O(n) process.

    As an aside, there's nothing special about frozenset, even creating a set from a set has O(n) time complexity:

    for i in [10**5, 10**6, 10**7]:
    a = set(range(i))
    %timeit set(a)

100 loops, best of 3: 3.33 ms per loop
10 loops, best of 3: 30.2 ms per loop
1 loop, best of 3: 421 ms per loop