What they're testing
Whether you understand Big-O as a reasoning tool or as a ritual to recite.
The short answer~30 seconds
Big-O describes how cost grows as input grows, dropping constants and lower-order terms. So no, O(1) isn't always faster: a constant-time operation with a large constant — hashing a long string, walking several layers of indirection — can be slower than a linear scan over 20 contiguous elements. Big-O answers "what happens when n is ten times bigger", not "which is faster right now".
The long answer
The detail most often omitted in practice is memory locality. Walking an array is far faster than walking a linked list of the same length, though both are O(n), because the array is contiguous so the CPU prefetches whole cache lines while the list is a random jump each step. The gap can be tens of times — larger than the difference between two adjacent complexity classes.
It's also worth separating average, worst and amortised cases. A HashMap is O(1) average and O(n) worst when every key collides. ArrayList.add is amortised O(1): most appends are constant, occasionally one is O(n) to double the array, and averaged out it's constant. In a latency-sensitive system, that "occasionally" is your p99.
What they'll ask next
?How do you count space complexity?
The AUXILIARY memory the algorithm allocates, excluding the input. So an in-place sort is O(1) space however large the array. With recursion, count the call stack — that's O(depth), and it's why deep recursion causes a StackOverflowError.
These lose points
- Saying "O(n log n) always beats O(n²)". At n = 10 it usually doesn't, and many libraries switch to insertion sort for small arrays for exactly that reason.
Elsewhere on this site
Sources
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, ch. 3