Чтобы ответить на этот вопрос, нужно разобраться, как списки устроены на низком уровне. Определение списка в исходниках CPython выглядит так: typedef struct {  PyObject_VAR_HEAD  PyObject **ob_item;  Py_ssize_t allocated; } PyListObject; Здесь ob_item -- это непрерывный массив указателей на элементы списка, а allocated содержит длину массива. Вот и все, что нужно знать, чтобы отвечать на вопросы о сложности операций со списками.  Во-первых, отсюда сразу видно, что получить длину массива можно очень быстро, за O(1), потому что не нужно пересчитывать все элементы...