First, does the candidate know what I'm talking about? Big-O notation and analysis is core curriculum for an undergraduate CS degree. Candidates straight out of school should be familiar from their algorithms or discrete math classes, even if they've never needed to analyze an algorithm since then. Industry candidates may have forgotten the term, but shouldn't be lost after a quick explanation like "you know, order n, order n squared, n log n, that sort of thing." Candidates that haven't been introduced to the concept are a red flag for me. I expect every candidate will have been asked this before in an interview.

Generally, good candidates will have immediate recall for well known data structures or algorithms. I try to ask a recall question as part of a larger problem. Like knowing the concept, candidates that don't immediately say that sorting is generally an O(n log n) problem are a red flag. Mentioning QuickSort's expected vs. worst-case performance is only marginally interesting, and I generally stop any candidate from explaining parallel quicksort or attempting to tell me about the tail distribution bound for a randomized version. Knowing and mentioning these variations shows plenty of theoretical depth, and my motivation for the recall question isn't to see if someone has taken a graduate-level class. I want to see explanation of an entire solution's runtime, not delve deeply into the minutia.

These questions are more than CS101. I often ask candidates to trade off between time and space complexity by throwing in some oddball requirement like constant memory. Typically making the required changes requires mental flexibility in the interview, as this comes up after someone has already been successful at solving the problem. I want to see how the candidates reacts to "great, you did exactly what I asked... now change it." I'm looking for the candidate to understand the changed circumstances and develop a solution that meets the new need. Does the candidate get stuck on their prior solution? Are they upset by the change? Do they forget about their old solution and try to start over completely? Ideally none of these things happen, and none have much to do with programming skill.