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?
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