When I implement something IRL (unless I'm implementing something from a paper or an algorithm that's well known), I typically can't just ask someone what the algorithmic complexity is. I have to determine if for myself.
Ed: to clarify a bit, in some cases the "non-optimal" solution is going to be the best one. And that's even before you start worrying about things like time/memory tradeoffs. When a candidate asks me questions along the lines of "which of the 2 input lists is bigger, what order of magnitude is the length, does XYZ fit in memory, etc", IMO it's a useful signal that shows they're aware of these tradeoffs.
The original question referred to "target runtime", which I take to me "basic expected performance characteristics." E.g. "Nothing crazy -- should run on a million integers or less, in half a second or less, which requiring not much more than the array size (or a small multiple) in extra memory. And worst case should be not too far from average case."
From there, I can start to think about the running complexity (or whether it even matters, for the scale given). But if an interviewer won't even tell me that ... I'd assume they're just like making candidates dance, for the sake of making them dance. While they sit back and stare at their phone, and occasionally interrupt with "hints".
Identifying a reasonable target runtime can be part of the problem. The longer they’ve been writing software, the more ambiguity I expect them to handle.
If the candidate wants to discuss performance, I’m obviously interested, but if they want me to serve a hint to them on a silver platter I’m just confused.
You know, like IRL. What this is supposedly about.
Again, the question referred to the target performance, not the optimal performance.