 <p><strong>Firstly,</strong> you have not measured the speed of <code>len()</code>, you have measured the speed of creating a list/set <em>together with</em> the speed of <code>len()</code>.</p> <p>Use the <code>--setup</code> argument of <code>timeit</code>:</p> <pre><code>$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)" 10000000 loops, best of 3: 0.0369 usec per loop $ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)" 10000000 loops, best of 3: 0.0372 usec per loop </code></pre> <p>The statements you pass to <code>--setup</code> are run before measuring the speed of <code>len()</code>.</p> <p><strong>Secondly,</strong> you should note that <code>len(a)</code> is a pretty quick statement. The process of measuring its speed may be subject to "noise". Consider that <a href="https://hg.python.org/cpython/file/3.5/Lib/timeit.py#l70">the code executed (and measured) by timeit</a> is equivalent to the following:</p> <pre><code>for i in itertools.repeat(None, number): len(a) </code></pre> <p>Because both <code>len(a)</code> and <code>itertools.repeat(...).__next__()</code> are fast operations and their speeds may be similar, the speed of <code>itertools.repeat(...).__next__()</code> may influence the timings.</p> <p>For this reason, you'd better measure <code>len(a); len(a); ...; len(a)</code> (repeated 100 times or so) so that the body of the for loop takes a considerably higher amount of time than the iterator:</p> <pre><code>$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)" 10000 loops, best of 3: 29.2 usec per loop $ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)" 10000 loops, best of 3: 29.3 usec per loop </code></pre> <p>(The results still says that <code>len()</code> has the same performances on lists and sets, but now you are sure that the result is correct.)</p> <p><strong>Thirdly,</strong> it's true that "complexity" and "speed" are related, but I believe you are making some confusion. The fact that <code>len()</code> has <em>O(1)</em> complexity for lists and sets does not imply that it must run with the same speed on lists and sets.</p> <p>It means that, on average, no matter how long the list <code>a</code> is, <code>len(a)</code> performs the same asymptotic number of steps. And no matter how long the set <code>b</code> is, <code>len(b)</code> performs the same asymptotic number of steps. But the algorithm for computing the size of lists and sets may be different, resulting in different performances (timeit shows that this is not the case, however this may be a possibility).</p> <p><strong>Lastly,</strong></p> <blockquote> <p>If the creation of a set object takes more time compared to creating a list, what would be the underlying reason?</p> </blockquote> <p>A set, as you know, does not allow repeated elements. Sets in CPython are implemented as hash tables (to ensure average <em>O(1)</em> insertion and lookup): constructing and maintaining a hash table is much more complex than adding elements to a list.</p> <p>Specifically, when constructing a set, you have to compute hashes, build the hash table, look it up to avoid inserting duplicated events and so on. By contrast, lists in CPython are implemented as a simple array of pointers that is <code>malloc()</code>ed and <code>realloc()</code>ed as required.</p>