Оригинальный комментарий:

А почему, кстати, О(1)? Уже придумали алгоритм, ищущий быстрее двоичного поиска?

Да, придумали. Хэш-таблица.

Вы привели контр-пример про строки (корректный, но являющийся скорее придиркой в данном контексте) — я на него ответил.

А если хэш-таблица не влезает в оперативку?

Это не влияет на ассимптотику.

А если таблицу надо часто перестраивать?

Это не влияет на ассимптотику.

А дальше попрошу сходить в любую книжку по алгоритмам и разобраться с понятием амортизированной сложности алгоритма

Я осознаю, что в случае хэш-таблицы это сложность в среднем, а в бин. поиске — в худшем случае. Но, как вы сказали, мы обсуждаем "какой алгоритм быстрее".

Так нормально? Вы меня не отсылайте в книжки, покажите где я по вашему неправ.
Я умею хэшировать строки и писать хэш-таблицы. И теорию тоже сдавал:) Так что давайте дискутировать предметно.