I had an interview with amazon before that went exactly like that. The question was asking for a search algorithm the answer I gave was O(n log n) if you ran it

I had an interview with amazon before that went exactly like that. The question was asking for a search algorithm the answer I gave was O(n log n) if you ran it the first time and O(1) every time after that. But the answer he wanted was O(n) every single time, wouldn't accept my explanation / answer.