Какова сложность доступа и поиска элементов в списке и словаре?

Для списка: доступ к элементу по индексу – O(1) (прямой индексированный доступ), а поиск элемента по значению – O(n) в худшем случае (линейный просмотр). Для словаря: доступ по ключу – амортизированно O(1) (хэш-таблица обеспечивает почти константное время поиска по ключу). Поиск по значению в словаре потребует перебора всех пар, что O(n), но обычно ищут именно по ключу.