Любая реализация списка будет иметь сложность O (n) для линейного поиска (например, list.index). Хотя, может быть, есть какие-то дурацкие реализации, которые делают хуже ...
Вы можете улучшить сложность поиска, используя различные структуры данных, такие как упорядоченные списки или наборы. Обычно они реализуются с помощью бинарных деревьев. Однако эти структуры данных накладывают ограничения на элементы, которые они содержат. В случае двоичного дерева элементы должны быть упорядочены, но стоимость поиска снижается до O (log n).
Как упоминалось ранее, посмотрите здесь стоимость времени выполнения стандартных структур данных Python:
http://wiki.python.org/moin/TimeComplexity