И непонятно, с чего вдруг это должно разваливать теорию оценок.
ну так проверка элемента вполне может включать в себя работу с тем же массивом. O(1) на элемент - это частный случай.
то частный случай. И в вопросе пользователя такого не было.

