Почему в js метод indexOf работает за О(n)?
Так indexOf не ищет по индексу значение, он ищет индекс по значению. O(1) это как раз обращение к массиву по индексу arr[0]
Никаким другим способом кроме прямого перебора нельзя ответить на вопрос «в каком ящике лежит foo?» кроме как открывать все ящики по очереди.