len(obj) simply calls obj.__len__():

>>> [1, 2, 3, 4].__len__()
4

It is therefore not correct to say that len() is always O(1) -- calling len() on most objects (e.g. lists) is O(1), but an arbitrary object might implement __len__ in an arbitrarily inefficient way.

max(obj) is a different story, because it doesn't call a single magic __max__ method on obj; it instead iterates over it, calling __iter__ and then calling __next__. It does this n times (and also does a comparison each time to track the max item it's seen so far), so it must always be at least O(n). (It can be slower if __next__ or the comparison methods are slow, although that would be very unusual.)

For either of these, we don't count the time it took to build the collection as part of the cost of calling the operation itself -- this is because you might build a list once and then call len() on it many times, and it's useful to know that the len() by itself is very cheap even if building the list was very expensive.

It's O(1) (constant time, not depending of actual length of the element - very fast) on every type you've mentioned, plus set and others such as array.array.

Inspecting the c-source of dictobject.c shows that the structure contains a member responsible for maintaining an explicit count (dk_size)

layout:
+---------------+
| dk_refcnt     |
| dk_size       |
| dk_lookup     |
| dk_usable     |
| dk_nentries   |
+---------------+
...

Thus it will have order O(1)

Firstly, you have not measured the speed of len(), you have measured the speed of creating a list/set together with the speed of len().

Use the --setup argument of timeit:

$ 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

The statements you pass to --setup are run before measuring the speed of len().

Secondly, you should note that len(a) is a pretty quick statement. The process of measuring its speed may be subject to "noise". Consider that the code executed (and measured) by timeit is equivalent to the following:

for i in itertools.repeat(None, number):
    len(a)

Because both len(a) and itertools.repeat(...).__next__() are fast operations and their speeds may be similar, the speed of itertools.repeat(...).__next__() may influence the timings.

For this reason, you'd better measure len(a); len(a); ...; len(a) (repeated 100 times or so) so that the body of the for loop takes a considerably higher amount of time than the iterator:

$ 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

(The results still says that len() has the same performances on lists and sets, but now you are sure that the result is correct.)

Thirdly, it's true that "complexity" and "speed" are related, but I believe you are making some confusion. The fact that len() has O(1) complexity for lists and sets does not imply that it must run with the same speed on lists and sets.

It means that, on average, no matter how long the list a is, len(a) performs the same asymptotic number of steps. And no matter how long the set b is, len(b) 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).

Lastly,

If the creation of a set object takes more time compared to creating a list, what would be the underlying reason?

A set, as you know, does not allow repeated elements. Sets in CPython are implemented as hash tables (to ensure average O(1) insertion and lookup): constructing and maintaining a hash table is much more complex than adding elements to a list.

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 malloc()ed and realloc()ed as required.

I guess you are missing one concept that is how a data structure can return its size in constant time i.e. O(1).

Roughly, think of a program like this:

void init(){
     // code to initialize (or allocate memory) the container 
     size = 0;
}
void add(Something something){
     container.add(something);
     size++;
}
void remove(Something something){
   //Code to search 'something'
   if(found) { 
    container.remove(something); 
    size--;
   }
}
int len(){
    return size;
}

Now any time you call the method len(), it is ready to return the integral value without any need to traverse the container.

Why strlen or any C related data structure doesn't work that way is because of the space overhead of having a counter like size. But that doesn't mean you can't define one. Hint: Use struct and keep the size maintained there.

In CPython time complexity is O(1) indeed. This fact can be deduced by looking at the source code of CPython (look at chepner's comment).

Lists can store their length as part of their structure. Since it only needs to be stored in one place, it can add a maximum of O(1) to all computations and therefore not be too much overhead.

Getting the length is therefore O(1) because it's just the lookup of a field.

For more information, see the docs.

Try assigning r.text to a local variable during your setup phase. It's a lazy property, not a plain attribute, and you're timing the work of constructing the value, which decodes from the internally cached bytes to str, not just the len call.

Hat tip to Martijn Pieters for the precise references!

Do you not have to iterate through the whole array to count how many indices its taking up?

No, you do not.

You can generally always trade space for time when constructing algorithms.

For example, when creating a collection, allocate a separate variable holding the size. Then increment that when adding an item to the collection and decrement it when removing something.

Then, voilà, the size of the collection can then be obtained in O(1) time just by accessing that variable.

And this appears to be what Python actually does, as per this page, which states (checking of the Python source code shows that this is the action when requesting the size of a great many objects):

Py_SIZE(o) - This macro is used to access the ob_size member of a Python object. It expands to (((PyVarObject*)(o))->ob_size).

If you compare the two approaches (iterating vs. a length variable), the properties of each can be seen in the following table:

In this case, the extra cost is minimal but the time saved for getting the length could be considerable, so it's probably worth it.

That's not always the case since, in some (rare) situations, the added space cost may outweigh the reduced time taken (or it may need more space than can be made available).

And, by way of example, this is what I'm talking about. Ignore the fact that it's totally unnecessary in Python, this is for a mythical Python-like language that has an O(n) cost for finding the length of a list:

import random

class FastQueue:
    """ FastQueue: demonstration of length variable usage.
    """
    def __init__(self):
        """ Init: Empty list and set length zero.
        """
        self._content = []
        self._length = 0

    def push(self, item):
        """ Push: Add to end, increase length.
        """
        self._content.append(item)
        self._length += 1

    def pull(self):
        """ Pull: Remove from front, decrease length, taking
                  care to handle empty queue.
        """
        item = None
        if self._length > 0:
            item = self._content[0]
            self._content = self._content[1:]
            self._length -= 1
        return item

    def length(self):
        """ Length: Just return stored length. Obviously this
                    has no advantage in Python since that's
                    how it already does length. This is just
                    an illustration of my answer.
        """
        return self._length

    def slow_length(self):
        """ Length: A slower version for comparison.
        """
        list_len = 0
        for _ in self._content:
            list_len += 1
        return list_len

""" Test harness to ensure I haven't released buggy code :-)
"""

queue = FastQueue()

for _ in range(10):
    val = random.randint(1, 50)
    queue.push(val)
    print(f'push {val}, length = {queue.length()}')

for _ in range(11):
    print(f'pull {queue.pull()}, length = {queue.length()}')

I checked it in a real condition and counting was 2 time or more faster than len().

My code that read two CSV format texts and then calculate number of lines is this:

import time
import csv

start_time = time.time()

psr = open('e_psr.txt')
cpr = open('e_cp.txt')

csv_psr = csv.reader(psr, delimiter=',')
csv_cp = csv.reader(cpr, delimiter=',')

csv_cp_copy = []
csv_psr_copy = []
r=0
e=0
for row in csv_psr:
    csv_psr_copy.append(row)
for row in csv_cp:
    csv_cp_copy.append(row)
e = len(csv_cp_copy)
r = len(csv_psr_copy)
psr.close()
cpr.close()

print(e,r)
print("\n--- %s seconds ---" % (time.time() - start_time))

and when I replaced len() with a simple counter in for loop (e += 1) the result significantly changed.

return with len():

10000 10000

--- 0.13390278816223145 seconds ---

return with counter:

10000 10000

--- 0.05642294883728027 seconds ---

In C strlen() is an O(n) operation because it has to scan for the \0 terminator. Very few languages use C's representation for strings. Most, including Python, store the length in a separate field so it doesn't have to be computed on demand.

See PEP 393 for an exact specification of how Python stores strings. It's complicated because it switches between representations to save space when strings consist solely of ASCII characters, but the field in question is the first one, length.

typedef struct {
  PyObject_HEAD
  Py_ssize_t length;                    // <--------------
  Py_hash_t hash;
  struct {
      unsigned int interned:2;
      unsigned int kind:2;
      unsigned int compact:1;
      unsigned int ascii:1;
      unsigned int ready:1;
  } state;
  wchar_t *wstr;
} PyASCIIObject;

typedef struct {
  PyASCIIObject _base;
  Py_ssize_t utf8_length;
  char *utf8;
  Py_ssize_t wstr_length;
} PyCompactUnicodeObject;

typedef struct {
  PyCompactUnicodeObject _base;
  union {
      void *any;
      Py_UCS1 *latin1;
      Py_UCS2 *ucs2;
      Py_UCS4 *ucs4;
  } data;
} PyUnicodeObject;

The fields have the following interpretations:

• length: number of code points in the string (result of sq_length)
• interned: interned-state (SSTATE_*) as in 3.2
• kind: form of string
  • 00 => str is not initialized (data are in wstr)
  • 01 => 1 byte (Latin-1)
  • 10 => 2 byte (UCS-2)
  • 11 => 4 byte (UCS-4);
• compact: the object uses one of the compact representations (implies ready)
• ascii: the object uses the PyASCIIObject representation (implies compact and ready)
• ready: the canonical representation is ready to be accessed through PyUnicode_DATA and PyUnicode_GET_LENGTH. This is set either if the object is compact, or the data pointer and length have been initialized.
• wstr_length, wstr: representation in platform's wchar_t (null-terminated). If wchar_t is 16-bit, this form may use surrogate pairs (in which cast wstr_length differs form length). wstr_length differs from length only if there are surrogate pairs in the representation.
• utf8_length, utf8: UTF-8 representation (null-terminated).
• data: shortest-form representation of the unicode string. The string is null-terminated (in its respective representation).

Full source code for the CPython string implementation is on GitHub.