pythonpython-3.xtime-complexitypython-collections

Algorithmic complexity to convert a set to a list in python

In python, when I convert my set to a list, what is the algorithmic complexity of such a task? Is it merely type-casting the collection, or does it need to copy items into a different data structure? What's happening?

I'd love to learn that the complexity was constant, like so many things in Python.

Solution

  • You can easily see this with a simple benchmark:

    import matplotlib.pyplot as plt


x = list(range(10, 20000, 20))
y = []
for n in x:
    s = set(range(n))
    res = %timeit -r2 -n2 -q -o list(s)
    y.append(res.best)


plt.plot(x, y)

    plot

    Which clearly shows a linear relationship -- modulo some noise.

    (EDITED as the first version was benchmarking something different).