Какое «time complexity» имеет операция list[element]?
https://wiki.python.org/moin/TimeComplexity

list в питоне — это по сути массив (точнее — вектор) указателей на *PyObject. Адрес начала известен. Размер элемента известен. Поэтому элементарная арифметика указателей адрес_начала + (sizeof(PyObject) * X) — за O(1)
Программа выполнится с 0(1), никакого чтения всего листа не произойдет. Потому что все вы делаете это получаете элемент по индексу. Например если изменить немножко вопрос скажем  у нас есть список и словарь.
'B' in ['A', 'B','C'] Вот это операция будет O(n)
В то время как
'B' in {'A':1,'B':2,'C':3} 
останется O(1).
Ну и напоследок если список отсортирован и python знает что он отсортирован то проверка на наличие элемнта в списке будет тоже O(1).

ОТРЕДАКТИРОВАНО 
Ну и напоследок если список отсортирован и python знает что он отсортирован то проверка на наличие элемнта в списке будет тоже O(1).
 
Это утверждение абсолютно неверно. На мою ошибку указал  Roman K В комментарии к моему ответу.